111 - Clondyke

Časový limit: 2s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3
Obtiažnosť:

Štandardná

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Uloha

Tom je zlatokop z Clondyke. Rad by si kupil parcelu, na ktorej by mohol tazit zlato. Cela mapa Clondyke sa da nakreslit ako obdlznik, rozdeleny na X x Y stvorcov (tzv. rajonov). Vsetky rajony maju rovnake rozmery. Podla pravidiel CFZ (Clondajkska federacia zlatokopov) musi kazdy kupeny pozemok splnat nasledujuce podmienky:

najmensou (nedelitelnou) castou je rajon
kazdy pozemok musi byt stvorec
kupna cena pozemku zavisi od poctu jeho rajonov (1 rajon stoji presne A$)

Tom by chcel zarobit co najviac, preto sa rozhodol, ze si da zalezat na vybere svojej parcely. Kazdy rajon na mape ohodnotil jedinym celym cislom = cenou zlata, ktore sa na nom nachadza. Napiste program, ktory precita Tomovu mapu a najde vhodny pozemok v sulade s pravidlami CFZ, z ktoreho by Tom vedel zarobit co najviac. (Teda Tom vytazi tolko zlata, kolko ho odhadol na svojej mape, avsak musi este zaplatit za kupeny pozemok).

Vstup

Prvy riadok vstupu bude obsahovat jedine cislo N, 1≤N≤100. Dalej bude nasledovat prazdny riadok a po nom N sad vstupu oddelenych takisto prazdnym riadkom. Kazda sada vstupu bude zacinat riadkom, v ktorom budu 3 cisla X,Y,A ( 1≤X≤100 - oznacuje pocet riadkov na Tomovej mape, 1≤Y≤100 - oznacuje pocet stlpcov na Tomovej mape, 1≤A≤1000 = kupna cena jedneho rajonu). V nasledujucich X riadkoch bude Y nezapornych celych cisel ≤ 1000, ktorymi je popisan� Tomova mapa.

Vystup

Pre kazdu sadu vstupu ma program vypisat jeden riadok tvaru: "Najvyhodnejsi pozemok ma zisk X." , kde X je najvyssi mozny zisk z nejakeho pozemku po zaplateni nakupnej ceny podla pravidiel CFZ. V pripade, ze sa na mape neda nic zarobit, program ma vypisat spravu: "Na ziadnom pozemku sa neda zarobit!"

Priklad

Vstup:

2

4 6 3
2 1 3 5 9 0
1 2 8 1 3 2
0 1 1 3 7 1
0 4 0 5 1 3

4 4 2
1 2 2 2
1 2 1 0
1 2 0 1
0 2 1 2

Vystup:

Najvyhodnejsi pozemok ma zisk 13.
Na ziadnom pozemku sa neda zarobit!

Problem by Jan Katrenic

Tréningové príklady