Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
24
1ºAlgorytmygrσfowe
NσdrzewieobokmrowiskσznσjdujesięwłσśnietσkσhodowlσmszycºMszyceżerująnσ
liściσchorσzwrozgσłęzieniσchdrzewσºWniektórychztychmiejscznσjdująsięrównież
mrówkipσtrolującedrzewoºDlσustσleniσuwσgi,mrówkisąponumerowσneodjeden
wgóręºHodowlizσgrσżσbiedronkσ,którσzσwszesiσdσnσdrzewietσm,gdziesąmszyce,
czylinσliściσchlubwrozgσłęzieniσchºWchwili,gdygdzieśnσdrzewieusiądziebiedronkσ,
mrówkipσtrolującedrzeworuszσjąwjejstronę,σbyjąprzegonićºKierująsięprzytym
nσstępującymizσsσdσmil
.
zkσżdegomiejscσnσdrzewie(liściσlubrozgσłęzieniσ)możnσdojśćdokσżdego
innegomiejscσ(bezzσwrσcσniσ)tylkonσjedensposób;kσżdσmrówkσwybierσ
włσśnietσkądrogędomiejscσlądowσniσbiedronki,
.
jeżeliwmiejsculądowσniσbiedronkiznσjdujesięmrówkσ,biedronkσnσtychmiσst
odlσtuje,
.
jeżelinσdrodze,odσktuσlnegopołożeniσmrówkidomiejscσlądowσniσbiedron-
ki,znσjdziesięinnσmrówkσ,totσpołożonσdσlejodbiedronkikończywędrówkę
izostσjewmiejscuswojegoσktuσlnegopołożeniσ,
.
jeżelidwielubwięcejmrówekpróbujewejśćnσtosσmorozgσłęzieniedrzewσ,torobi
totylkojednσmrówkσTtσznσjmniejszymnumerem,σresztσmrówekpozostσje
nσswoichmiejscσch(liściσchlubrozgσłęzieniσch),
.
mrówkσ,którσdocierσdomiejscσlądowσniσbiedronki,przegσniσjąipozostσje
wtymmiejscuº
BiedronkσjestupσrtσiznowulądujenσdrzewieºWówczσsmrówkiponownieruszσją,
σbyprzegonićintruzσº
Dlσuproszczeniσprzyjmujemy,żeprzejściegσłązkiłączącejliśćzrozgσłęzieniemlub
łączącejdwσrozgσłęzieniσzσjmujewszystkimmrówkomjednostkęczσsuº
Zadanie
Nσpiszprogrσm,któryl
.
wczytσopisdrzewσ,początkowepołożeniσmrówekorσzmiejscσ,wktórychkolejno
siσdσbiedronkσ,
.
dlσkσżdejmrówkiznσjdziejejkońcowepołożenieiwyznσczyliczbęmówiącą,ile
rσzyprzegoniłσonσbiedronkęº
wejście
Wpierwszymwierszuwejściσznσjdujesięjednσliczbσcσłkowitσ
n
,równσłącznejliczbie
liściirozgσłęzieńwdrzewie,
1<n<5000
ºPrzyjmujemy,żeliścieirozgσłęzieniσsą
ponumerowσneod
1
do
n
ºWkolejnych
n−1
wierszσchsąopisσnegσłązkiTwkσżdym
ztychwierszysązσpisσnedwieliczbycσłkowite
a
i
b
oznσczσjące,żedσnσgσłązkσ
łączymiejscσ
a
i
b
ºGσłązkipozwσlσjąnσprzejściezkσżdegomiejscσnσdrzewiedo
kσżdegoinnegomiejscσºW(
n+1
)-szymwierszujestzσpisσnσjednσliczbσcσłkowitσ
k
,
1<k<1000
,
k<n
,równσliczbiemrówekpσtrolującychdrzewoºWkσżdymzkolejnych
k
wierszyzσpisσnσjestjednσliczbσcσłkowitσzprzedziσłuod
1
do
n
ºLiczbσzσpisσnσ
wwierszu
n+1+i
oznσczσpoczątkowepołożeniemrówkinr
i
ºWkσżdymmiejscu(liściu
lubrozgσłęzieniu)możeznσjdowσćsięconσjwyżejjednσmrówkσºWwierszu
n+k+2
