Fişierul intrare/ieşire:coliziuni.in, coliziuni.outSursăAlgoritmiada 2015 Runda Finala
AutorTeodor PlopAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test2 secLimită de memorie100000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Coliziuni

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.

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ă 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. 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ţă?

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ M ≤ 50.000
  • 1 ≤ T ≤ 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 ≤ 2000, M ≤ 500

Exemplu

coliziuni.incoliziuni.out
3
3 2
> 1 1
< 1 3
2 2
^ 1 2
< 2 2
2 2
> 1 1
< 2 2
1
3
-1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?