== include(page="template/taskheader" task_id="piete") ==
Poveste şi cerinţă...
Într-o ţară există $N$ oraşe, fiecare oraş având o piaţă unde oamenii pot vinde şi cumpăra articole. Sunt $M$ tipuri de articole care se comercializează şi fiecare piaţă are propriul ei preţ de vânzare şi cumpărare pentru oricare dintre cele $M$ articole, nu neapărat diferit de cel din alte pieţe. Fiind fată deşteaptă, Claudia şi-a dat seama că poate să facă profit cumpărând articole dintr-un oraş şi vânzându-le în alt oraş. Ea îşi propune să-şi sporească economiile achiziţionând şi vânzând produse în pieţele din ţară şi să ajungă la o sumă finală pe care poate să o şi depăşească.
Datorită sistemului strict impus de către regele tiran, comerţul în ţară este descurajat. Regele a impus ca nimeni să nu poată călători dintr-un oraş în altul având mai multe articole de acelaşi tip şi îi obligă pe toţi comercianţii ce intră într-un oraş să îşi vândă toate articolele aduse, înainte de a face alte achiziţii. De asemenea, la orice transport de articole dintr-un oraş în altul, comerciantul respectiv va primi o bulină neagră în condica regelui.
h2. Cerinţă
Scrieţi un program care să o ajute pe Claudia să ajungă cel puţin la suma finală dorită, cu un număr minim de buline negre înregistrate în condica regelui.
h2. Date de intrare
Fişierul de intrare $piete.in$ ...
Pe prima linie a fişierului $piete.in$ se află patru numere naturale nenule $N$, $M$, $S$, $F$ separate prin câte un spaţiu, cu semnificaţia: $N$ – numărul de oraşe; $M$ – numărul de tipuri de articole din fiecare piaţă; $S$ – o sumă de bani ce reprezintă economiile iniţiale ale Claudiei; $F$ - o sumă de bani ce reprezintă suma finală dorită. Pe următoarele $N$ linii se află câte $M$ numere separate prin câte un spaţiu: al $j$-lea număr de pe linia $i$ reprezintă preţul de vânzare/cumpărare a articolului $j$ în piaţa $i$.
h2. Date de ieşire
În fişierul de ieşire $piete.out$ ...
Pe prima linie a fişierului $piete.out$ se găseşte numărul minim de buline negre pe care le va primi Claudia, dacă reuşeşte să ajungă cel puţin la suma $F$. Dacă ea nu are nicio modalitate să ajungă la suma $F$ atunci se va afişa $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10$
* $1 ≤ M ≤ 10$
* $1 ≤ S ≤ F ≤ 100$
* $0 ≤ p[i, j] ≤ 100$ $p[i, j] =$ preţul articolului $j$ la piaţa $i$
* există drum direct între oricare două oraşe
* în orice piaţă, preţul de vânzare al unui articol este acelaşi cu preţul de cumpărare al acestuia
h2. Exemplu
table(example). |_. piete.in |_. piete.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 4 10 20
5 1 16 4
4 2 13 3
6 3 20 5
| 2
|
h3. Explicaţie
Cumpără articolele $1$, $2$ şi $4$ din oraşul $1$ (rămâne cu $0$ bani). Merge în oraşul $3$ şi le vinde. Are acum $14$ bani şi o bulină neagră. Cumpără articolul $3$ din oraşul $2$ ( $1$ ban rămas). Merge în oraşul $3$ şi îl vinde. Are acum $21$ bani şi $2$ buline. A obţinut suma dorită şi numărul de buline negre este minim.
table(example). |_. piete.in |_. piete.out |
| 2 3 3 6
4 7 8
6 5 9
| -1
|
h3. Explicaţie
...
Nu poate cumpăra niciun articol deci nu are cum să facă profit
== include(page="template/taskfooter" task_id="piete") ==
== include(page="template/taskfooter" task_id="piete") ==
