Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tester.in, tester.out | Sursă | Algoritmiada 2010, Runda 1 |
| Autor | Cosmin Gheorghe | Adăugată de |  Stefan-Alexandru Filip •Prostu |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tester
Gigel este o persoana cu pasiune pentru jocurile pe calculator, asa ca s-a angajat ca tester. Gigel a primit sarcina de a analiza un joc cu N stari. El poate face M mutari de tipul (u, v) avand semnificatia ca din starea u trece in starea v. El stie ca doua comenzi executate consecutiv pot produce anumite efecte pe care vrea sa le descopere. Gigel porneste din orice stare a jocului si incepe sa execute comenzi. El nu are mult timp la dispozitie asa ca doreste sa stie o secventa de a executa comenzi astfel incat oricare doua comenzi (u, v) si (v, w) sa existe consecutiv in secventa. Jocul poate fi resetat, o resetare inseamna reinceperea jocului din orice stare. Se doreste o secventa cu numar minim de resetari, iar in caz de egalitate se doreste o secventa cu numar minim de comenzi.
Date de intrare
Fişierul de intrare tester.in contine pe prima linie doi intregi, N si M. Pe urmatoarele M linii se afla cate doi intregi u si v, avand semnificatia din enunt.
Date de ieşire
În fişierul de ieşire tester.out va contine un sirul de stari pe care Gigel trebuie sa il parcurga pentru a testa jocul. O resetare va fi codificata prin litera R.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ 5000
- Orice solutie care respecta conditiile din enunt va obtine punctajul pe respectivul test.
Exemplu
| tester.in | tester.out |
|---|---|
| 5 5 1 2 2 3 3 5 5 4 2 4 | 1 2 3 5 4 R 1 2 4 |
| 4 7 1 2 2 3 3 2 1 4 4 3 3 4 3 1 | 1 2 3 2 3 4 3 2 3 1 4 3 4 3 1 |
Explicaţie
Pentru primul exemplu, comenzile executate sunt (1, 2) (2, 3) (3, 5) (5, 4) - (1, 2) (2, 4) se observa ca orice doua comenzi posibil consecutive apar in secventa.
