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:

  • x-1 : redukujemy liczbę chwastów wyłącznie na polu x (bo x-1 i x-2 są puste)
  • x : redukujemy liczbę chwastów na polach x i być moźe x+1 (bo x-1 jest puste)
  • x+1 : redukujemy liczbę chwastów na polach x i być może x+1 oraz x+2 
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 ).

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com