Diferente pentru problema/sudest intre reviziile #30 si #20

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="sudest") ==
 
Fermierul Ion detine un teren de forma patrata, impartit in $NxN$ patrate de latura unitate, pe care cultiva cartofi. Pentru recoltarea cartofilor fermierul foloseate un robot special proiectat in acest scop. Robotul porneste din patratul din stanga sus, de coordonate $(1,1)$ si trebuie sa ajunga in patratul din dreapta jos, de coordonate $(N,N)$. Traseul robotului este programat prin memorarea unor comenzi pe o cartela magnetica. Fiecare comanda specifica directia de deplasare (sud sau est) si numarul de patrate pe care le parcurge in directia respectiva. Robotul strange recolta doar din patratele in care se opreste intre doua comenzi. Din pacate, cartela pe care se afla programul s-a deteriorat si unitatea de citire a robotului nu mai poate distinge directia de deplasare, ci numai numarul de pasi pe care trebuie sa-i faca robotul la fiecare comanda. Fermierul Ion trebuie sa introduca manual, pentru fiecare comanda, directia de deplasare.
Fermierul Ion detine un teren de forma patrata, impartit in $NxN$ patrate de latura unitate, pe care cultiva cartofi. Pentru recoltarea cartofilor fermierul foloseate un robot special proiectat in acest scop. Robotul porneste din patratul din stanga sus, de coordonate (1,1) si trebuie sa ajunga in patratul din dreapta jos, de coordonate ($N$, $N$). Traseul robotului este programat prin memorarea unor comenzi pe o cartela magnetica. Fiecare comanda specifica directia de deplasare (sud sau est) si  numarul de patrate pe care le parcurge in directia respectiva. Robotul strange recolta doar din patratele in care se opreste intre doua comenzi. Din pacate, cartela pe care se afla programul s-a deteriorat si unitatea de citire a robotului nu mai poate distinge directia de deplasare, ci numai numarul de pasi pe care trebuie sa-i faca robotul la fiecare comanda. Fermierul Ion trebuie sa introduca manual, pentru fiecare comanda, directia de deplasare.
h2. Cerinta
h2. Date de intrare
Fisierul de intrare $sudest.in$ are urmatoarea structura: Pe prima linie se afla numarul natural $N$, reprezentand dimensiunea parcelei de teren. Pe urmatoarele $N$ linii se afla cate $N$ numere naturale, separate prin spatii, reprezentand cantitatea de cartofi din fiecare patrat unitate. Pe linia $N+2$ se afla un numar natural $K$ reprezentand numarul de comenzi aflate pe cartela magnetica. Pe linia $N+3$ se afla $K$ numerele naturale $C$~1~, $C$~2~, ..., $C$~K~, separate prin spatii, reprezentand numarul de pasi pe care trebuie sa-i efectueze robotul la fiecare comanda.
Fisierul de intrare $sudest.in$ are urmatoarea structura: Pe prima linie se afla numarul natural $N$, reprezentand  dimensiunea parcelei de teren. Pe urmatoarele $N$ linii se afla cate $N$ numere naturale, separate prin spatii, reprezentand cantitatea de cartofi din fiecare patrat unitate. Pe linia $N+2$ se afla un numar natural $K$ reprezentand numarul de comenzi aflate pe cartela magnetica. Pe linia $N+3$ se afla $K$ numerele naturale $C$<sub>1</sub>, $C$<sub>2</sub>, ...,$C$<sub>K</sub>, separate prin spatii, reprezentand numarul de pasi pe care trebuie sa-i efectueze robotul la fiecare comanda.
 
h2. Date de iesire
Fisierul de iesire $sudest.out$ va contine pe prima linie cantitatea maxima de cartofi recoltata de robot. Pe urmatoarele $K+1$ linii vor fi scrise, in ordine, coordonatele patratelor unitate ce constituie traseul pentru care se obtine cantitate maxima de cartofi, cate un patrat unitate pe o linie. Coordonatele scrise pe aceeasi linie vor fi separate printr-un spatiu. Primul patrat de pe traseu va avea coordonatele $1 1$, iar ultimul va avea coordonatele $N N$. Daca sunt mai multe trasee pe care se obtine o cantitate maxima de cartofi recoltata se va afisa unul dintre acestea.
Fisierul de iesire $sudest.out$ va contine pe prima linie cantitatea maxima de cartofi recoltata de robot. Pe urmatoarele $K+1$ linii vor fi scrise, in ordine, coordonatele patratelor unitate ce constituie traseul pentru care se obtine cantitate maxima de cartofi, cate un patrat unitate pe o linie. Coordonatele scrise pe aceeasi linie vor fi separate printr-un spatiu. Primul patrat de pe traseu va avea coordonatele 1 1, iar ultimul va avea coordonatele N N. Daca sunt mai multe trasee pe care se obtine o cantitate maxima de cartofi recoltata se va afisa unul dintre acestea.
h2. Restrictii
* $5 &le; N &le; 100$
* $2 &le; K &le; 2*N-2$
* {$1 &le; C{~1~}, ..., C{~K~} &le; 10$}
* Cantitatea de cartofi dintr-un patrat de teren este numar natural intre $0$ si $100$.
* 1 &le; C<sub>1</sub>, ..., C<sub>K</sub> &le; 10
* Cantitatea de cartofi dintr-un patrat de teren este numar natural intre 0 si 100.
* Pentru fiecare set de date de intrare se garanteaza ca exista cel putin un traseu.
* Se considera ca robotul strange recolta si din patratul de plecare $(1,1)$ si din cel de sosire $(N,N)$.
* Se considera ca robotul strange recolta si din patratul de plecare (1,1) si din cel de sosire ($N$,$N$).
 
h2. Exemplu
h3. Explicatie
Un alt traseu posibil este:
$1$ $1$
$1$ $3$
$1$ $5$
$2$ $5$
$6$ $5$
$6$ $6$
dar costul sau este $1+1+4+1+5+10=22.$
 
== include(page="template/taskfooter" task_id="sudest") ==
1 1
1 3
1 5
2 5
6 5
6 6
dar costul sau este 1+1+4+1+5+10=22
== include(page="template/taskfooter" task_id="sudest") ==

Diferente intre securitate:

task: sudest
public

Diferente intre topic forum:

2058