Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
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



Wersja do druku