== include(page="template/taskheader" task_id="zidar") ==
Poveste si cerinta...
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:
# 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);
# 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);
# numarul de caramizi folosite in constructia zidului nu trebuie sa depaseasca un numar natural {$X$}.
!problema/zidar?zidar.gif!
h2. 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.
h2. 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).
h2. 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.
h2. 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$}.
h2. Exemplu
table(example). |_. zidar.in |_. zidar.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicatie
...
!problema/zidar?exemplu.bmp!
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.
== include(page="template/taskfooter" task_id="zidar") ==
== SmfTopic(topic_id="...") ==
