Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | gard4.in, gard4.out | Sursă | lot 2006 |
| Autor | Dan-Ionut Fechete | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.55 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gard 4
Praslea cel Voinic a gasit gradina cu meri cu mere de aur, dar are acum probleme cu paza acestora. A stat treaz ani la rand pana cand a decis sa construiasca un gard in jurul lor, astfel incat sa poata dormi linistit. Gradina are forma unui patrat cu latura N metri. Praslea a impartit gradina in N*N patrate de 1 m2, patrate aranjate pe N linii (numerotate de la 1 la N) si N coloane (numerotate de la 1 la N). Fiecare mar se afla in unul dintre aceste patrate. Pentru a construi gardul, Praslea a decis sa selecteze un sir de patrate in care primul si ultimul patrat, precum si oricare 2 patrate consecutive in sir au cel putin un punct comun. Un patrat poate fi ales în sir o data sau de mai multe ori. In fiecare patrat din sir Praslea va plasa un stalp urias. Gardul format din acesti stalpi imparte gradina in doua zone (interior si exterior). Toti merii trebuie sa se afle in interior. Un patrat este considerat in interior daca nu exista drum de la un patrat situat pe marginea gradinii (linia 1, coloana 1, linia N sau coloana N) la patratul respectiv. Un drum este un sir de patrate, astfel incat oricare doua patrate consecutive pe drum au o latura comuna, patratele de pe drum fiind libere (patrate care nu contin stalpi).
Plasarea unui stalp intr-un anumit patrat are un anumit cost. Daca un patrat apare de mai multe ori in sirul ales de Praslea atunci costul va fi adunat de tot atatea ori la costul total.
Cerinta
Scrieti un program care sa determine costul total minim de construire a gardului respectand conditiile din enunt.
Date de intrare
Date de iesire
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| gard4.in | gard4.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
