Diferente pentru problema/coliziuni intre reviziile #8 si #14

Nu exista diferente intre titluri.

Diferente intre continut:

Alinuţa are de compus pentru şcoală o poezie despre furnici. Da, chiar aşa este, nu vă mint... De aceea, fetei i-a venit ideea că ar fi bine să studieze aceste *insecte sociale* înainte să îşi ducă la bun sfârşit această temă de mare importanţă.
Aşa că Alinuţa şi-a cumpărat $M$ furnici, şi le-a aşezat pe toate într-o matrice de dimensiuni $N x N$. Fiecare furnică ocupă astfel exact o pătrăţică din matrice. Alinuţa le-a dat furnicilor şi o direcţie iniţială (fiecare furnică este îndreptată într-una din cele $4$ direcţii $(N, S, E, V)$, codificate $(^, v, >, <)$. Sper că totul este clar până aici. Chiar nu vă mint.
Aşa că Alinuţa şi-a cumpărat $M$ furnici, şi le-a aşezat pe toate într-o matrice de dimensiuni $N x N$. Fiecare furnică ocupă astfel exact o pătrăţică din matrice. Alinuţa le-a dat furnicilor şi o direcţie iniţială (fiecare furnică este îndreptată într-una din cele $4$ direcţii $(N, S, E, V)$, codificate $(^, v, >, <)$. Sper că totul este clar până aici.
Iar acum, Alinuţa a început să studieze aceste furnici şi a observat că în fiecare secundă, toate furnicile fac un pas în direcţia către care sunt îndreptate. Fiind însă nişte insecte algoritmice, ele ştiu că nu trebuie să părăsească matricea. Aşa că, în secunda în care sunt pe cale de a ieşi din aceasta, ele preferă în schimb să se întoarcă cu 180 grade. Nu cred că s-a înţeles foarte bine... Hai să luăm un exemplu.
Liniile şi coloanele matricii sunt numerotate de la $1$ la $N$. Dacă la secunda $T$ o furnică se află pe căsuţa $(1, N)$ şi se îndreaptă către $EST (>)$, atunci la secunda $T + 1$ ea se va afla tot pe căsuţa $(1, N)$ dar va fi îndreptată către $VEST (<)$.
Liniile şi coloanele matricii sunt numerotate de la $1$ la $N$. Dacă la secunda $T$ o furnică se află spre exemplu pe căsuţa $(1, N)$ şi se îndreaptă către $EST (>)$, atunci la secunda $T + 1$ ea se va afla tot pe căsuţa $(1, N)$ dar va fi îndreptată către $VEST (<)$.
Iar acum, cerinţa. Alinuţa vrea să ştie după câte secunde se vor întâlni pentru prima oară două furnici în această matrice. Ea consideră că două furnici se întâlnesc dacă păşesc în aceeaşi secundă pe acelaşi pătrăţel din matrice. Oare are vreun sens să o ajutaţi pe Alinuţa să găsească răspunsul la această cerinţă?
Iar acum, cerinţa. Alinuţa vrea să ştie după câte secunde se vor întâlni pentru prima oară două furnici în această matrice. Ea consideră că două furnici se întâlnesc dacă păşesc în aceeaşi secundă pe acelaşi pătrăţel din matrice. Daca nu exista doua furnici care sa se intalneasca vreodata afisati doar -1. Oare are vreun sens să o ajutaţi pe Alinuţa să găsească răspunsul la această cerinţă?
h2. Date de intrare
Fişierul de intrare $coliziuni.in$ conţine pe prima linie numerele $N$ şi $M$, având semnificaţia din enunţ. Pe fiecare linie din următoarele $M$ se vor găsi direcţia furnicii (reprezentată printr-un caracter $^, v, >, <$), şi două numere naturale $X$ şi $Y$, reprezentând poziţia iniţială a furnicii.
Fişierul de intrare $coliziuni.in$ conţine pe prima linie numărul de teste, $T$. Fiecare test are următoarea structură: pe prima linie se află numerele $N$ şi $M$, având semnificaţia din enunţ. Pe fiecare linie din următoarele $M$ se vor găsi direcţia furnicii (reprezentată printr-un caracter $^, v, >, <$), şi două numere naturale $X$ şi $Y$, reprezentând poziţia iniţială a furnicii.
h2. Date de ieşire
În fişierul de ieşire $coliziuni.out$ se va găsi un singur număr natural, reprezentând numărul de secunde după care se vor întâlni pentru prima oară două furnici între ele.
În fişierul de ieşire $coliziuni.out$ se vor găsi $T$ linii cu câte un număr intreg fiecare, reprezentând numărul de secunde după care se vor întâlni pentru prima oară două furnici între ele, sau $-1$ daca nu se intampla vreodata asta, pentru fiecare test în parte.
h2. Restricţii
* $... &le; ... &le; ...$
* $1 &le; N &le; 1.000.000$
* $1 &le; M &le; 50.000$
* $1 &le; T &le; 1000$
* Suma tuturor valorilor lui $M$ în cadrul aceluiaşi fişier de intrare nu va depăşi valoarea $250.000$.
* Pentru 40% din punctaj: $T = 10, N &le; 2000, M &le; 500$
h2. Exemplu
table(example). |_. coliziuni.in |_. coliziuni.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|3
3 2
> 1 1
< 1 3
2 2
^ 1 2
< 2 2
2 2
> 1 1
< 2 2
| 1
3
-1
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="coliziuni") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.