Diferente pentru problema/alee intre reviziile #24 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 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.
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
h2. Date de intrare
Fisierul de intrare <i>alee.in</i> 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 X1 Y1 X2 Y2, separate prin cate un spatiu, reprezentand pozitiile celor doua porti (X1, Y1 reprezinta linia si respectiv coloana zonei ce contine prima poarta, iar X2, Y2 reprezinta linia si respectiv coloana zonei ce  contine cea de a doua poarta).
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 <i>alee.out</i> va contine o singura linie pe care va fi scris un numar natural care reprezinta numarul minim de dale necesare pentru construirea aleii.
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 &le; N &le; 200
* 1 &le; M &le; N*N
* $1 &le; N &le; 175$
* $1 &le; M &le; 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 class="example" cellspacing="0"><tr><th>alee.in</th><th>alee.out</th></tr><tr><td>
8 6<br />
2 7<br />
3 3<br />
4 6<br />
5 4<br />
7 3<br />
7 5<br />
1 1 8 8<br />
</td><td>15</td></tr></table>
table(example). |_. alee.in |_. alee.out |
| 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