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.
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ś.