Runda 2: Planowanie potopu
24.06.2009
Zło szerzy się w Bajtocji: król nie dba o losy kraju, mafia terroryzuje stolicę, policja jest skorumpowana, dorośli nieodpowiedzialni, a dzieci nie chodzą do szkoły. Jedyną szansą dla pogrążonej w chaosie Bajtocji jest odrodzenie w wodach oczyszczającego potopu. Potop, który trzeba jednak najpierw dokładnie zaplanować. Bajtocja ma kształt prostokąta, który dla wygody dzielimy na w kolumn, po h pól w każdej. Dla każdego pola określona jest jego wysokość nad poziomem morza. Jest pewne szczególne pole, źródło wszelkiego zła, na które spuścimy ulewę. Deszcz będzie padał tylko tam, jednak na szczęście woda, której użyjemy do potopu, rozlewa się oraz ścieka w dół. Dlatego nawet deszcz padający tylko w jednym miejscu po odpowienio długim czasie zawsze zaleje całą Bajtocję. Aby odnieść zamierzony skutek chcemy zalać conajmniej k pól. Jednak z drugiej strony mamy dobre serce i chcemy zalać jak najmniej pól (ale zawsze co najmniej k). Twoim zadaniem jest wyznaczenie obszaru, który należy zalać. WejścieW pierwszej linii wejścia dane są liczby w, h, x0, y0, k (1 ≤ w, h ≤ 1000, 1 ≤ x0 ≤ w, 1 ≤ y0 ≤ h, 1 ≤ k ≤ w * h), oznaczające odpowiednio - ilość kolumn i wierszy mapy, pozycję źródła wszelkiego zła oraz minimalną liczbę pól, którą chcemy zalać. Następnie dana jest mapa w postaci h linii, z których każda zawiera w dodatnich liczb całkowitych nie większych od 106 - są to wysokości pól. WyjścieNa wyjściu należy wypisać h linii po w znaków każda, tworzących mapkę Bajtocję po powodzi. Zalane pola należy oznaczyć znakiem PrzykładŹródło wszelkiego zła wyróżniono kolorem niebieskim, a (przykładowe) pasmo górskie wyróżniono kolorem czerwonym. Spuszczając ulewę na źrodło wszelkiego zła możemy zalać dziewięć pól nie przekraczając pasma górskiego (przykład drugi). Aby zalać dziesiąte pole, musimy zalać również jakieś pole z pasma górskiego, co prowadzi jednak do zalania całej Bajtocji - cóż (przykład pierwszy). Dane 1: kod: FLOODPLAN, limity: 4 s, 32 MB |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com