In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Bajtocja słynie z bogatych złóż złota, dlatego przez długie lata kwitła sprzedaż tego kruszcu do sąsiedniego królestwa, Bitlandii. Niestety powiększająca się ostatnio dziura budżetowa zmusiła króla Bitlandii do wprowadzenia zaporowych ceł na metale i minerały. Handlarze przekraczający granicę muszą zapłacić 50% wartości przewożonego ładunku. Bajtockim kupcom grozi bankructwo. Na szczęście bajtoccy alchemicy opracowali sposoby pozwalające zamieniać pewne metale w inne. Pomysł kupców polega na tym, aby z pomocą alchemików zamieniać złoto w pewien tani metal, a następnie, po przewiezieniu go przez granicę i zapłaceniu niewielkiego cła, znowu otrzymywać z niego złoto. Niestety alchemicy nie znaleźli sposobu na zamianę dowolnego metalu w dowolny inny. Może się więc zdarzyć, że proces otrzymania danego metalu ze złota musi przebiegać wielostopniowo i że na każdym etapie uzyskiwany będzie inny metal. Alchemicy każą sobie słono płacić za swoje usługi i dla każdego znanego sobie procesu zamiany metalu w metal wyznaczyli cenę za przemianę 1 kg surowca. Handlarze zastanawiają się, w jakiej postaci należy przewozić złoto przez granicę, oraz jaki ciąg procesów alchemicznych należy zastosować, aby zyski były możliwie największe.
Pomóż uzdrowić bajtocką gospodarkę! Napisz program, który:
W pierwszym wierszu standardowego wejścia znajduje się jedna dodatnia liczba całkowita oznaczająca liczbę rodzajów metali, . W wierszu o numerze , dla , znajduje się nieujemna parzysta liczba całkowita - cena 1 kg metalu oznaczonego numerem , . Przyjmujemy, że złoto ma numer 1. W wierszu o numerze znajduje się jedna nieujemna liczba całkowita równa liczbie procesów przemiany znanych alchemikom, . W każdym z kolejnych wierszy znajdują się po trzy liczby naturalne, pooddzielane pojedynczymi odstępami, opisujące kolejne procesy przemiany. Trójka liczb oznacza, że alchemicy potrafią z metalu o numerze otrzymywać metal o numerze i za zamianę 1 kg surowca każą sobie płacić bajtalarów, . Uporządkowana para liczb i może się pojawić w danych co najwyżej jeden raz.
Twój program powinien pisać na standardowe wyjście. W pierwszym wierszu powinna zostać wypisana jedna liczba całkowita - koszt wykonania wyznaczonego ciągu procesów alchemicznych powiększony o płacone na granicy cło.
Dla danych wejściowych:
4 200 100 40 2 6 1 2 10 1 3 5 2 1 25 3 2 10 3 4 5 4 1 50
poprawną odpowiedzią jest:
60
Autor zadania: Łukasz Kowalik.