Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | zmeu.in, zmeu.out | Sursă | ad-hoc |
| Autor | Cosmin Bondane | Adăugată de |  Bondane Cosmin •cos_min |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 6144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zmeu
Farfurel si-a gasit in sfarsit iubirea, pe Sarah. Din pacate aceasta este inchisa intr-un turn si este pazita de zmeul cel rau. Cheltuind foarte multi bani, Farfurel a reusit sa faca rost de harta spre turn. Harta este codificata sub forma a 2 matrici: A si B, de dimensiuni NxN. Valoarea pozitiei (i,j) a matricei A reprezinta gradul de pericol pentru ca Farfurel sa ajunga in pozitia respectiva. Valoarea pozitie (i,j) a matricei B reprezinta costul ca pozitia respectiva sa aiba pericolul nul. Stiind ca pericolul se conserva, iar daca acesta depaseste o valoare P, Farfurel devine hrana zmeului. Ajutati-l pe Farfurel aflat in pozitia (1,1) sa ajunga la Sarah aflata in pozitia (N,N) cu cat mai putini bani posibil.
Date de intrare
Pe prima linie a fisierului de intrare se gasesc doua numre intregi N si P, numarul de linii si coloane a matricelor A si B, respectiv pericolul maxim admis. Pe urmatoarele 2*N linii se regasesc cate N numere intregi care descriu matricea A, respectiv matricea B.
Date de iesire
Pe singura linie a fisierului de intrare se va afisa suma minima necesara lui Farfurel sa isi indeplineasca misiunea.
Restrictii
- 1 ≤ P ≤ 500
- 1 ≤ N ≤ 100
- 0 ≤ valoarea elementelor matricei A ≤ P
- 0 ≤ valoarea elementelor matricei B ≤ 109
- A[1][1] = A[N][N] = B[1][1] = B[N][N] = 0
Exemplu
| zmeu.in | zmeu.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
