Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-27 21:56:15.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:clear.in, clear.outSursăHappy Coding 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.5 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Clear

Fermierul Ionica are un teren de forma dreptunghiulara, impartit in MxN zone unitare (M este numarul de linii, iar N este numarul de coloane). In urma poluarii generate de uzina din apropiere, o parte dintre zone au fost afectate, astfel incat in zonele acelea nu mai poate fi cultivata momentan nici o planta. Pentru a putea cultiva din nou plante in acele zone, fermierul Ionica va trebui sa curete zonele respective. Pentru aceasta, el poate inchiria niste utilaje pentru indepartarea poluarii. Fiecare utilaj va fi amplasat initial intr-o zona afectata. Din zona initiala, un utilaj poate fi deplasat in orice zona afectata adiacenta (pe orizontala sau verticala) si asa mai departe, pana cand utilajul ajunge intr-o zona finala, de unde firma de la care a inchiriat fermierul utilajul va veni sa il ridice. Fiecare zona prin care trece un utilaj este curatata complet (inclusiv zona initiala si cea finala).

Firma care inchiriaza utilajele ofera 2 tipuri de contracte de inchiriere. Primul tip de contract permite amplasarea unui utilaj in orice zona afectata, deplasarea acestuia prin oricate zone afectate (poate sa nu fie deplasat deloc din zona initiala) si ridicarea acestuia din orice zona finala. Al doilea tip de contract permite amplasarea unui utilaj in orice zona afectata, insa pune conditia ca utilajul sa fie deplasat prin cel putin 4 zone afectate distincte (inclusiv zona initiala), iar zona finala sa fie aceeasi cu zona initiala. In cazul ambelor tipuri de contracte se permite inchirierea oricarui numar de utilaje.

Fermierul Ionica are si el propriile lui conditii. Un utilaj inchiriat nu trebuie sa treaca de mai multe ori prin aceeasi zona (cu exceptia zonei initiale, in cazul tipului 2 de contract), iar prin zonele neafectate nu trebuie sa treaca nici un utilaj. De asemenea, el doreste ca prin fiecare zona afectata sa treaca exact un singur utilaj.

Cunoscand tipul de contract ales de fermierul Ionica, dimensiunile terenului si pozitiile zonelor afectate de poluare, determinati numarul minim de utilaje pe care trebuie sa le inchirieze fermierul.

Date de intrare

Prima linie a fisierului de intrare clear.in contine 3 numere intregi: X, M si N. X reprezinta tipul contractului semnat cu firma de inchiriere. Urmatoarele M linii contin cate N caractere din multimea {'0','1'}. Daca al j-lea caracter de pe a i-a dintre aceste M linii este 1, atunci zona de pe linia i si coloana j este afectata de poluare; in cazul in care caracterul este 0, zona respectiva nu este afectata.

Date de iesire

In fisierul de iesire clear.out veti afisa numarul minim de utilaje pe care trebuie sa le inchirieze fermierul Ionica. Daca nu exista nici o posibilitate de a inchiria utilaje astfel incat sa fie satisfacute toate conditiile ambelor parti, atunci afisati -1.

Restrictii

  • 1 ≤ X ≤ 2
  • 1 ≤ M ≤ 333
  • Daca X = 1, atunci 1 ≤ N ≤ 7
  • Daca X = 2, atunci 1 ≤ N ≤ 10
  • 50% din teste vor avea X = 1 (restul de 50% vor avea X = 2).

Exemplu

clear.inclear.out
1 3 4
1101
0111
1111
2
2 3 4
1101
0111
1111
-1
2 6 6
011111
010001
111101
101101
100001
111111
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?