problema/zona

Zona

Scrie aici despre problema/zona

== include(page="template/taskheader" task_id="zona") ==
 
Ionut pleaca in drumetie intr-o portiune de teren de forma patratica cu latura de $N$ metri. O harta a zonei are trasat un caroiaj care imparte zona in $N*N$ patrate unitate, cu latura de $1$ metru. Astfel harta zonei are aspectul unui tablou patratic cu $N$ linii si $N$ coloane. Liniile si coloanele sunt numerotate de la $1$ la $N$. Elementele tabloului bidimensional corespund patratelor unitate. Zona poate fi parcursa strabatand oricare dintre laturile patratelor unitate cel mult o singura data.
Ionut pleaca din punctul aflat in coltul din dreapta jos al patratului unitate din linia $X$, coloana $Y$ si se deplaseaza facand un pas (parcurgand o latura a unui patrat unitate) in una din directiile Nord, Est, Sud, Vest. Pentru a retine mai usor traseul foloseste urmatoarea codificare pentru cele $4$ directii: $1$ pentru deplasarea spre Nord, $2$ pentru deplasarea spre Est, $3$ pentru deplasarea spre Sud, respectiv $4$ pentru deplasarea spre Vest.
Ajung intr-alt punct (colt de patrat unitate), Ionut continua sa se deplaseze fara a trece de mai multe ori pe aceeasi latura a unui patrat unitate. Ionut se opreste in momentul in care ajunge intr-un punct prin care a mai trecut. Traseul strabatut intre cele doua treceri prin acelasi punctu delimiteaza o zona de teren formata din patrate unitate.
 
!problema/zona?zona1.jpg!
 
h2. Cerinta
 
Dandu-se linia $X$ si coloana $Y$ corespunzatoare pozitiei de plecare a lui Ionut, dimensiunea zonei $N$, lungimea traseului $L$ si traseul determinati:
 
# Numarul de pasi parcursi intre prima si a doua trecere prin punctul de oprire.
# Numarul de patrate unitate interioare zonei delimitata de traseul strabatut intre cele doua treceri prin acelasi punct.
 
h2. Date de intrare
 
Pe prima linie a fisierului $zona.in$ se afla valorile $X$ $Y$ $N$ $L$ despartite prin cate un spatiu, reprezentand coordonatele punctului de plecare, dimensiunea terenului si lungimea traseului parcurs. Pe urmatoarea linie se afla $L$ valori din multimea ${$1$, $2$, $3$, $4$}$ despartite prin cate un spatiu, reprezentand codificarea intregului traseu.
 
h2. Date de ieşire
 
Fisierul $zona.out$ va contine doua linii, pe prima linie un numar natural reprezentand raspunsul la cerinta $1)$, iar pe linia a doua, un numar natural reprezentand raspunsul la cerinta $2)$.
 
h2. Restricţii
 
* $0 < N < 51$
 
* $0 < X, Y < N$
 
* $0 < L < 2501$
 
* Se garanteaza faptul ca traseul trece de doua ori prin acelasi punct si nu parcurge de doua ori aceeasi latura.
 
* Pentru determinarea corecta a numarului de la punctul $1)$ se acorda $20%$ din punctaj.
 
* Pentru determinarea corecta a numarului de la punctul $2)$ se acorda $80%$ din punctaj.
 
* In situatia in care nu ati reusit sa rezolvati cerinta $1)$, dar aveti un raspuns pentru $2)$, veti scrie raspunsul pentru cerinta $2)$ pe linia $2$ si nu pe prima linie!
 
h2. Exemplu
 
table(example). |_. zona.in |_. zona.out |
| 2 3 7 18
  2 3 3 3 4 3 4 1 1 1 1 1 2 2 2 3 3 4
| 16
  11
|
 
h3. Explicaţie
 
Dupa cei $18$ pasi de la plecare ajunge in punctul situat in coltul din dreapta jos al patratului unitate de coordonate $(3,4)$. Ultimii $16$ pasi parcursi delimiteaza $11$ patrate unitate.
 
!problema/zona?zona2.jpg!
 
== include(page="template/taskfooter" task_id="zona") ==
 

public

task: zona

9944