Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | coliziuni.in, coliziuni.out | Sursă | Algoritmiada 2015 Runda Finala |
| Autor | Teodor Plop | Adăugată de |  Mihai Calancea •klamathix |
| Timp execuţie pe test | 1 sec | Limită de memorie | 100000 kbytes |
| Scorul tău | N/A | Dificultate | N/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. Chiar nu vă mint.
Iar acum, Alinuţa a început să observe 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 (<).
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ţă?
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.
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.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| coliziuni.in | coliziuni.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
