|
VIII Olimpiada Informatyczna 2000/2001
|
|
Zadanie: MRO
|
Autor: Krzysztof Loryś
|
Mrówki i biedronka
| Zawody II stopnia, dzień drugi |
8 luty 2001
|
| Plik źródłowy: | MRO.??? (np. pas, c, cpp) |
| Plik wykonywalny: | MRO.exe |
| Plik wejściowy: | MRO.in |
| Plik wyjściowy: | MRO.out |
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:
- z każdego miejsca na drzewie (liścia lub rozgałęzienia) można
dojść do każdego innego miejsca (bez zawracania) tylko na jeden
sposób; każda mrówka wybiera właśnie taką drogę do miejsca
lądowania biedronki,
- jeżeli w miejscu lądowania biedronki znajduje się mrówka,
biedronka natychmiast odlatuje,
- jeżeli na drodze, od aktualnego położenia mrówki do miejsca
lądowania biedronki, znajdzie się inna mrówka, to ta położona dalej
od biedronki kończy wędrówkę i zostaje w miejscu swojego
aktualnego położenia,
- jeżeli dwie lub więcej mrówek próbuje wejść na to samo rozgałęzienie
drzewa, to robi to tylko jedna mrówka --- ta z najmniejszym numerem,
a reszta mrówek pozostaje na swoich miejscach
(liściach lub rozgałęzieniach),
- mrówka, która dociera do miejsca lądowania biedronki, przegania ją
i pozostaje w tym miejscu.
Biedronka jest uparta i znowu ląduje na drzewie.
Wówczas mrówki ponownie ruszają, aby przegonić intruza.
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.
Zadanie
Napisz program, który:
- wczyta z pliku wejściowego MRO.IN opis drzewa,
początkowe położenia mrówek oraz miejsca, w których
kolejno siada biedronka,
- dla każdej mrówki znajdzie jej końcowe położenie
i wyznaczy liczbę mówiącą, ile razy przegoniła
ona biedronkę.
Wejście
W pierwszym wierszu pliku tekstowego MRO.OUT znajduje się jedna
liczba całkowita n, równa łącznej liczbie liści i rozgałęzień w drzewie,
1<=n<=5000.
Przyjmujemy, że liście i rozgałęzienia są ponumerowane od 1 do n.
W kolejnych n-1 wierszach są opisane gałązki --- w każdym z tych
wierszy są zapisane dwie liczby całkowite a i b oznaczające,
że dana gałązka łączy miejsca a i b.
Gałązki pozwalają na przejście z każdego miejsca na drzewie, do
każdego innego miejsca.
W n+1-szym wierszu jest zapisana jedna liczba całkowita k,
1<=k<=1000 i k<=n, równa liczbie mrówek patrolujących drzewo.
W każdym z kolejnych k wierszy zapisana jest jedna liczba całkowita
z przedziału od 1 do n.
Liczba zapisana w wierszu n+1+i oznacza początkowe położenie
mrówki nr i.
W każdym miejscu (liściu lub rozgałęzieniu) może znajdować się co
najwyżej jedna mrówka.
W wierszu n+k+2 zapisana jest jedna liczba całkowita l, 1<=l<=500,
mówiąca ile razy biedronka siada na drzewie.
W każdym z kolejnych l wierszy zapisana jest jedna liczba całkowita
z zakresu od 1 do n.
Liczby te opisują kolejne miejsca, w których siada biedronka.
Wyjście
Twój program powinien zapisać k wierszy
w pliku wyjściowym MRO.OUT. W i-tym wierszu powinny zostać
zapisane dwie liczby całkowite oddzielone pojedynczym odstępem ---
końcowa pozycja i-tej mrówki (numer rozgałęzienia lub liścia) i
liczba mówiąca, ile razy przegoniła ona biedronkę.
Przykład
Dla pliku wejściowego MRO.IN:
4
1 2
1 3
2 4
2
1
2
2
2
4
|
|
poprawną odpwiedzią jest plik wyjściowy MRO.OUT:
1 0
4 2