Autor zadania: Marcin Dublański
Niech H oznacza największą możliwą wysokość pola na działce Pana Józefa. Z warunków zadania wiemy, że H <= 10000.
Pierwszy algorytm korzystał będzie z wyszukiwania binarnego. Zauważmy, że jeżeli zalejemy pole z pompą na wysokość h i spowoduje to zalanie jakiegoś drzewa, to pompowanie do osiągnięcia wysokości większej tym bardziej nie uniknie zalania niepożądanego pola. Z drugiej strony, jeżeli poziom wody osiągając poziom h nie zalewa żadnego drzewa, to zalanie działki na wysokość mniejszą niż h tym bardziej nie spowoduje zalania pola z drzewem. Te spostrzeżenia prowadzą nas do następującego algorytmu:
można = 0; // na pewno osiągając poziom 0 nie zalejemy żadnego drzewa
nie_można = H+1; // na pewno osiągając poziom H+1 zalejemy jakieś drzewo
while (można+1 < nie_można) do // dopóki nie znamy poszukiwanej granicy
środek = (można+nie_można) / 2;
if( można_zalać_na_wysokość(środek) ) można = środek;
else nie_można = środek;
endwhile
wynik = ile_pól_zalano_jeśli_osiągnieto_wysokość( można );
Widać, że pętla while wykona się tylko O(log H) razy. Pozostaje napisać funkcję:
można_zalać_na_wysokość( h ):
kolejka q;
q.dodaj( pole_z_pompą );
while (q jest niepusta) do
w = q.początek; q.usuń_początek;
if( w to pole z drzewem owocowym ) return false;
dla_każdego v = sąsiad w
if( v nie był jeszcze odwiedzony i wysokość v jest <= h)
q.dodaj(v);
enddla_każdego
endwhile
return true;
Widać, że funkcja ta to nic innego jak drobna modyfikacja przeszukiwania wszerz. Działa ona liniowo ze względu na ilość pól, czyli w O(n*m). Cały algorytm działa więc w czasie: O(n*m* log H) i rozsądnie zaimplementowany dawał maksymalną liczbę punktów.
W programie wzorcowym zaimplementowany został algorytm działający w czasie O(n*m). Idea bazuje na H+1 kolejkach q[0], q[1], ..., q[H]. Przez kolejkę q[i] przejdą wszystkie pola, które na pewno zostaną zalane, jeśli wysokość wody nad pompą osiągnie wartość dokładnie i.
Algorytm ten wygląda tak:
q[0].dodaj( pole_z_pompą );
h = 0;
wynik = 0;
while (h <= H) do
zalano_teraz = 0;
while (q[h] jest niepusta) do
w = q.początek; q.usuń_początek;
zalano_teraz = zalano_teraz+1;
if( w to pole z drzewem owocowym ) return wynik; // nie można zalewać do wysokości h
dla_każdego v = sąsiad w
if( v nie był jeszcze odwiedzony )
hh = wysokość v;
if( hh <= h ) q[h].dodaj(v);
else q[hh].dodaj(v);
enddla_każdego
endwhile
wynik = wynik+zalano_teraz;
h = h+1;
endwhile
return wynik;
Widać, że rzeczywiście każde pole jest odwiedzane tylko jeden raz. Złożoność algorytmu jest więc O(n*m).
