Nu aveti permisiuni pentru a descarca fisierul grader_test2.in
Diferente pentru problema/alee intre reviziile #4 si #53
Diferente intre titluri:
alee
Alee
Diferente intre continut:
== include(page="template/taskheader" task_id="alee") ==
Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari. Parcul are forma unui patrat cu latura de n metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in NxN zone patrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice patratice cu N linii si N coloane. Liniile si respectiv coloanele sunt numerotate de la 1 la N. Elementele matricei corespund zonelor patrate de latura 1 metru. O astfel de zona poate sa contina un copac sau este libera. Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de 1 metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta.
Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari. Parcul are forma unui patrat cu latura de $N$ metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in $N*N$ zone patrate cu latura de $1$ metru. Astfel harta parcului are aspectul unei matrice patratice cu $N$ linii si $N$ coloane. Liniile si, respectiv, coloanele sunt numerotate de la $1$ la $N$. Elementele matricei corespund zonelor patrate de latura $1$ metru. O astfel de zona poate sa contina un copac sau este libera. Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de $1$ metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta. h2. Cerinta Scrieti un program care sa determine numarul minim de dale necesare pentru construirea unei alei continue de la o poarta la cealalta.
h2. Date de intrare
...
Fisierul de intrare $alee.in$ contine pe prima linie doua valori naturale $N$ si $M$ separate printr-un spatiu, reprezentand dimensiunea parcului, respectiv numarul de copaci care se gasesc in parc. Fiecare dintre urmatoarele $M$ linii contine cate doua numere naturale $X$ si $Y$ separate printr-un spatiu, reprezentand pozitiile copacilor in parc ({$X$} reprezinta linia, iar $Y$ reprezinta coloana zonei in care se afla copacul). Ultima linie a fisierului contine patru numere naturale {$X{~1~}$}, {$Y{~1~}$}, {$X{~2~}$}, {$Y{~2~}$}, separate prin cate un spatiu, reprezentand pozitiile celor doua porti ( {$X{~1~}$}, {$Y{~1~}$} reprezinta linia si respectiv coloana zonei ce contine prima poarta, iar {$X{~2~}$}, {$Y{~2~}$} reprezinta linia si respectiv coloana zonei ce contine cea de a doua poarta).
h2. Date de iesire
...
Fisierul de iesire $alee.out$ va contine o singura linie pe care va fi scris un numar natural care reprezinta numarul minim de dale necesare pentru construirea aleii.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 175$ * $1 ≤ M ≤ N*N$ * Aleea este continua daca oricare doua placi consecutive au o latura comuna. * Aleea incepe cu zona unde se gaseste prima poarta si se termina cu zona unde se gaseste cea de a doua poarta. * Pozitiile portilor sunt distincte si corespund unor zone libere. * Pentru datele de test exista intotdeauna solutie.
h2. Exemplu table(example). |_. alee.in |_. alee.out |
| This is some text written on multiple lines. | This is another text written on multiple lines.
| 8 6 2 7 3 3 4 6 5 4 7 3 7 5 1 1 8 8 | 15
| h3. Explicatie
...
O modalitate de a construi aleea cu numar minim de dale este: @O O O _ _ _ _ _@ @_ _ O O _ _ X _@ @_ _ X O _ _ _ _@ @_ _ _ O O X _ _@ @_ _ _ X O _ _ _@ @_ _ _ _ O O _ _@ @_ _ X _ X O O _@ @_ _ _ _ _ _ O O@ (cu X sunt marcati copacii, cu _ zonele libere, iar cu O dalele aleii).
== include(page="template/taskfooter" task_id="alee") ==
Nu exista diferente intre securitate.
Diferente intre topic forum:
2075