| Fişierul intrare/ieşire: | mingiute.in, mingiute.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 16 |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
Mingiute
Intr-un camin oarecare de la periferia orasului locuieste un adolescent rebel, pe numele sau Matei Mingiuta. Dornic de afirmare, acesta patrunde prin efractie in subsolul cladirii si sustrage intreaga rezerva de dero a caminului cu scopul de a o monetiza pe seama colegilor creduli. Din pacate pentru Mingiuta, mafia turceasca a sesizat rapid lipsa detergentului prin mirosul greu al elevilor barbosi, iar el este cel dintai suspect intrucat, nu de mult, a incercat sa vanda la plic gazonul din fata biroului directorului.
Cladirea caminului este alcatuita din N etaje, fiecare etaj avand M camere. Pentru a scapa de orice urma, Mingiuta imparte prada in primul rand pe etaje, aproximand pentru fiecare etaj un numar de nri pliculete de dero. Camerele fiearui etaj sunt numerotate de la 1 la M. Din pacate pentru el, pe fiecare etaj se afla un paracios care supravegheaza o zona continua de camere pe la mijlocul holului. In acest caz, el poate comercializa pliculetele doar in primele sti si ultimele dri camere ale fiecarui etaj 1 ≤ i ≤ N, maxim unul pe camera.
O alta problema ar fi ca mirosul generat de consumul de dero este extrem de volatil si se ridica la etajele superioare. Caminul este proiectat in asa fel incat oricare doua camere numerotate la fel sa se afle una sub alta. Astfel, daca se consuma dero in doua camere numerotate la fel, de pe etaje diferite, mirosul va deveni prea puternic si Mingiuta va fi prins.
In caz contrar, probabilitatea ca Mingiuta sa fie prins ramane direct proportionala cu diferenta absoluta maxima intra pliculetele distribuite la inceputul holului si cele distribuite la sfarsitul acestuia pentru fiecare etaj in parte. Deci, cu cat maximul dintre diferentele absolute intre numarul de pliculetele distribuite in primele sti si ultimele dri camere este mai mic, cu atat Mingiuta are sanse mai mari sa scape basma curata.
Sa se scrie un program care determina aceasta diferenta absoluta minima pentru a-l ajuta pe Mingiuta sa decida daca isi va asuma riscul sau va consuma singur intreaga cantitate de dero. In cazul in care el nu poate sa distribuie in siguranta prada afisati "-1", soarta acestuia fiind pecetluita.
Date de intrare
In fisierul de intrare mingiute.in se afla pe prima linie numerele N si M, urmand ca pe urmatoarele N linii sa fie descrise etajele caminului prin trei intregi sti dri nri.
Date de ieşire
In fisierul de iesire se va afisa pe o singura linie mingiute.out raspunsul problemei.
Restricţii
- 1 ≤ N ≤ 200
- 1 ≤ M ≤ 200
- sti <= M-dri pentru oricare 1 ≤ i ≤ N
- 0 ≤ nri ≤ M
- Mingiuta este doar o porecla pe care prietenii i-au dat-o dupa forma punctajului la OJI
- Orice asemanare cu personaje reale este pur intamplatoare, autorul a conceput problema dupa ce s-a uitat prea mult la "Breaking Bad"
Exemplu
| mingiute.in | mingiute.out |
|---|---|
| 6 10 5 3 2 2 4 2 3 2 1 4 4 3 2 3 1 4 5 1 | 1 |
Explicaţie
O distribuite optima ar putea fi:
- Etaj 1: camerele 5,9
- Etaj 2: camerele 1,10
- Etaj 3: camera 3
- Etaj 4: camerele 4,7,8
- Etaj 5: camera 2
- Etaj 6: camera 6
Diferenta maxima intre pliculetele distribuite la inceputul holului si cele de la sfarsitul acestuia apare pentru etajele 3-6 si este egala cu 1.
