Fişierul intrare/ieşire:zidar.in, zidar.outSursăONI 2007, clasa 10
AutorAdrian VladuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Zidar

Nu se stie de ce, ai decis subit sa incepi o cariera in constructii. Zidurile pe care le construiesti sunt formate din caramizi cubice de latura 1, asezate in mai multe straturi.
Pentru a proiecta un astfel de zid, ai trasat un caroiaj format din MxN patrate de latura 1, organizate in M linii si N coloane. Liniile caroiajului sunt numerotate de la 1 la M, incepand de jos in sus, iar coloanele sunt numerotate de la 1 la N de la stanga la dreapta.

Fiecare casuta a caroiajului are asociat un anumit cost, care trebuie platit in cazul in care plasam o caramida in casuta respectiva. Costul construirii unui zid este egal cu suma costurilor casutelor in care sunt plasate caramizile zidului.
Zidurile tale trebuie sa respecte urmatoarele conditii:

  1. fiecare strat de caramizi este format dintr-o singura secventa de caramizi, oricare doua caramizi consecutive fiind adiacente (mai exact, caramizile de pe un strat sunt plasate in casute ale caroiajului situate pe aceeasi linie, pe coloane consecutive);
  2. cel putin o caramida de pe fiecare strat i trebuie sa fie asezata pe o alta caramida de pe stratul de dedesubt (i-1); cel mai de jos strat trebuie sa fie asezat pe pamant (pamantul fiind sub linia 1 a caroiajului);
  3. numarul de caramizi folosite in constructia zidului nu trebuie sa depaseasca un numar natural X.

Cerinta

Fiind un zidar dornic de afirmare si stiind ca dispui de o suma de T euro, calculeaza numarul maxim de caramizi pe care le poti folosi in constructia unui zid care costa cel mult T euro.

Date de intrare

Fisierul de intrare zidar.in contine pe prima linie patru numere naturale M N X T separate prin cate un spatiu cu semnificatia din enunt. Pe fiecare dintre urmatoarele M linii se afla cate N numere naturale cuprinse intre 1 si 100 reprezentand costul asezarii unei caramizi pentru fiecare dintre casutele caroiajului (mai precis, elementul j de pe a (i+1)-a linie a fisierului de intrare reprezinta costul asezarii unei caramizi in casuta de pe linia i si coloana j a caroiajului).

Date de iesire

Fisierul de iesire zidar.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul maxim de caramizi pe care il poate contine zidul tau, respectand conditiile impuse.

Restrictii

  • 1 ≤ M ≤ 50
  • 1 ≤ N ≤ 20
  • 1 ≤ X ≤ 60
  • 1 ≤ T ≤ 10000
  • Pentru 30% din teste T ≤ 60. Pentru 60% din teste N ≤ 10.

Exemplu

zidar.inzidar.out
4 5 20 8
2 2 3 2 1
4 7 1 2 3
2 1 1 1 1
1 2 5 7 3
6

Explicatie

Pentru a construi zidul marcat in figura ai nevoie de exact 8 euro. Nu se pot construi ziduri cu mai multe caramizi folosind aceasta suma de bani.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content