Dalsze kłopoty z ogrodem (omówienie)
03.05.2011
To zadanie okazało się najprostszym z zadań drugiej rundy. Pan Wincenty ma do dyspozycji jeden rodzaj operacji - zmniejszenie o połowę liczby chwastów w każdym z trzech sąsiednich pól w dowolnym miejscu ogrodu. Należy obliczyć ile minimalnie razy będzie musiał wykonywać tę operację, zanim usunie wszystkie chwasty. Zauważmy, że łatwo można ustalić jak pan Wincenty powinien postąpić z chwastami w pierwszym od lewej niepustym polu ogrodu. Oznaczmy numer tego pola przez x. Wiadomo, że chwasty z pola x kiedyś trzeba będzie usunąć. Wiadomo także, że po ich lewej stronie na pewno nie ma żadnych chwastów. W takim razie niezależnie od rozmieszczenia pozostałych chwastów w ogrodzie, chwasty z pola x warto usuwać wybierając jako cel miotacza ognia pole nr x+1, tj. pole o jeden na prawo od tego, które aktualnie rozważamy. Wynika to stąd, że z trzech możliwości wyboru celu operacji:
trzecia możliwość jest jednoznacznie najlepsza. Po usunięciu wszystkich chwastów z pola x można kontynuować stosowanie tego rozumowania dla kolejnych pierwszych-niepustych pól aż do momentu oczyszczenia ogrodu. To prowadzi do rozwiązania zachłannego o złożoności O(N) ( właściwie O(N*log(MaxC)), jeśli doliczymy czas potrzebny na kolejne dzielenia przez dwa ). |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com