platforma |
|
Miruna s-a decis recent să intre în afacerile cu petrol. Ea doreşte să construiască o platformă petrolieră pe Marea Albă. Această mare este foarte interesantă deoarece are forma unui dreptunghi de dimensiuni N şi M, putând fi astfel reprezentată sub forma unei matrice. Pentru fiecare zonă reprezentată de către un element al matricei, se cunoaşte adâncimea apei mării în zona respectivă. Platforma pe care Miruna doreşte să o construiască trebuie sa aibă dimensiunile A şi B. Deoarece pilonii necesari construcţiei costă foarte mult, se doreşte minimizarea adâncimii maxime a unei zone unde va urma să se construiască platforma.
Cerinţă Dându-se o matrice cu N linii şi M coloane reprezentând Marea Albă, determinaţi o submatrice de dimensiuni A şi B - poziţia de construcţie a platformei - astfel încât elementul maxim din submatrice să fie cât mai mic.Date de intrare Fişierul de intrare platforma.in conţine pe prima linie patru numere naturale N, M, A şi B. Pe urmatoarea linie se vor afla M numere întregi reprezentând prima linie a matricei care codifică fundul mării. Pentru a afla celelalte elemente ale matricei veţi folosi formula: Element[i][j]=(Element[i-1][j]*i)% 666013, i>1 (atenţie la generarea numerelor, aveţi nevoie de întregi pe 64 de biţi).Date de ieşire Fişierul de ieşire platforma.out va conţine un singur număr natural, reprezentând adâncimea maximă a zonei deasupra căreia va trebui să fie construită platforma.Restricţii
Exemplu
|