Polish version    English version  
  Historia OI -> XIII OI 2005/2006


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Orka

Limit pamięci: 64 MB

Rolnik Bajtazar chce zaorać pole w kształcie prostokąta. Bajtazar może zacząć od zaorania jednej skiby z dowolnego boku pola, potem może zaorać jedną skibę z dowolnego boku niezaoranej części pola itd., aż całe pole będzie zaorane. Po zaoraniu każdej kolejnej skiby, niezaorana część pola ma kształt prostokąta. Skiby mają szerokość 1, a długość i szerokość pola wyrażają się liczbami całkowitymi i .

Niestety Bajtazar do orki ma tylko jedną słabowitą szkapę. Gdy szkapa zacznie orać skibę, to nie zatrzymuje się, aż zaorze ją do końca. Bajtazar musi uważać, jeżeli zaoranie skiby będzie dla szkapy zbyt wielkim wysiłkiem, to szkapa padnie. Po zaoraniu każdej kolejnej skiby szkapa może odpocząć i nabrać sił. Nie wszystkie miejsca na polu są tak samo trudne do zaorania. Bajtazar dokładnie zna swoje pole i dokładnie wie jak trudno się orze w każdym miejscu.

Podzielmy pole na kwadratów jednostkowych. Kwadraty będziemy identyfikować za pomocą ich współrzędnych , dla i . Każdemu z kwadratów jest przypisany jego współczynnik trudności orki - nieujemna liczba całkowita. Współczynnik trudności orki kwadratu o współrzędnych będziemy oznaczać przez . Dla każdej skiby suma współczynników trudności orki kwadratów tworzących skibę nie może przekroczyć pewnej ustalonej stałej - w przeciwnym przypadku szkapa padnie.

Bajtazar stoi przed trudnym zadaniem. Przed zaoraniem każdej skiby musi zdecydować z którego boku niezaoranej części pola ją zaorać, tak żeby szkapa nie padła. Z drugiej strony, chciałby żeby było jak najmniej skib.

Zadanie

Napisz program, który:

  • wczyta ze standardowego wejścia liczby , i , oraz współczynniki trudności orki,
  • wyznaczy, w jaki sposób Bajtazar powinien zaorać pole,
  • wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy dodatnie liczby całkowite: , i , pooddzielane pojedynczymi odstępami, , , . W kolejnych wierszach znajdują się współczynniki trudności orki. Wiersz zawiera współczynniki , pooddzielane pojedynczymi odstępami, .

Wyjście

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą: minimalną liczbę skib powstałych po zaoraniu pola zgodnie z podanymi warunkami. Możesz założyć, że dla danych wejściowych, pole zawsze da się zaorać zgodnie z warunkami podanymi w zadaniu.

Dla danych wejściowych:
12 6 4
6 0 4 8 0 5
0 4 5 4 6 0
0 5 6 5 6 0
5 4 0 0 5 4
8

Powyższy rysunek przedstawia przykładowy sposób zaorania pola.




Wersja do druku