W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Jak wiadomo, mrówki potrafią "hodować" mszyce. Mszyce wydzielają słodką rosę miodową, którą spijają mrówki. Mrówki zaś bronią mszyc przed ich największymi wrogami - biedronkami.
Na drzewie obok mrowiska znajduje się właśnie taka hodowla mszyc. Mszyce żerują na liściach oraz w rozgałęzieniach drzewa. W niektórych z tych miejsc znajdują się również mrówki patrolujące drzewo. Dla ustalenia uwagi, mrówki są ponumerowane od jeden w górę. Hodowli zagraża biedronka, która zawsze siada na drzewie tam, gdzie są mszyce, czyli na liściach lub w rozgałęzieniach. W chwili, gdy gdzieś na drzewie usiądzie biedronka, mrówki patrolujące drzewo ruszają w jej stronę, aby ją przegonić. Kierują się przy tym następującymi zasadami:
Dla uproszczenia przyjmujemy, że przejście gałązki łączącej liść z rozgałęzieniem lub łączącej dwa rozgałęzienia, zajmuje wszystkim mrówkom jednostkę czasu.
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita , równa łącznej liczbie liści i rozgałęzień w drzewie, . Przyjmujemy, że liście i rozgałęzienia są ponumerowane od 1 do . W kolejnych wierszach są opisane gałązki - w każdym z tych wierszy są zapisane dwie liczby całkowite i oznaczające, że dana gałązka łączy miejsca i . Gałązki pozwalają na przejście z każdego miejsca na drzewie, do każdego innego miejsca. W -szym wierszu jest zapisana jedna liczba całkowita , i , równa liczbie mrówek patrolujących drzewo. W każdym z kolejnych wierszy zapisana jest jedna liczba całkowita z przedziału od 1 do . Liczba zapisana w wierszu oznacza początkowe położenie mrówki nr . W każdym miejscu (liściu lub rozgałęzieniu) może znajdować się co najwyżej jedna mrówka. W wierszu zapisana jest jedna liczba całkowita , , mówiąca ile razy biedronka siada na drzewie. W każdym z kolejnych wierszy zapisana jest jedna liczba całkowita z zakresu od 1 do . Liczby te opisują kolejne miejsca, w których siada biedronka.
Twój program powinien wypisać na standardowe wyjście wierszy. W -tym wierszu powinny zostać zapisane dwie liczby całkowite oddzielone pojedynczym odstępem - końcowa pozycja -tej mrówki (numer rozgałęzienia lub liścia) i liczba mówiąca, ile razy przegoniła ona biedronkę.
Dla danych wejściowych:
4 1 2 1 3 2 4 2 1 2 2 2 4
poprawną odpowiedzią jest:
1 0 4 2
Autor zadania: Krzysztof Loryś.