| Fişierul intrare/ieşire: | robo.in, robo.out | Sursă | ACM ICPC - Romanian Programming Contest 2016 |
| Autor | Matei Popovici | Adăugată de |  Stefan Ruseti •stefanr |
| Timp execuţie pe test | 1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Robo
ROBO este un robot care poate executa o secventa de actiuni pentru a repara o statie orbitala. ROBO are senzori care ii permit sa detecteze "starea curenta" in care se afla statia. O stare de succes corespunde situatiei in care statia a fost reparata. Starea curenta si actiunea aleasa de ROBO determina in mod unic starea urmatoare. Un exemplu este ilustrat mai jos:
In exemplul de mai sus, starile sunt reprezentate prin noduri (cercuri). Actiunile eticheteaza muchiile dintre noduri. Starea initiala este "0", iar cea de succes este 4.
Analizand modelul de mai sus, ROBO observa ca poate realiza reparatia daca executa secventa de actiuni aba (trecand prin starile 0,1,4), dar si daca executa bbba (trecand prin starile 0,2,3,2,4). ROBO crede ca poate inlocui modelul sau intern, ilustrat mai sus, cu un model mai bun, adica unul in care:
* numarul de stari este mai mic;
* exact aceleasi secvente de actiuni conduc la reparatia statiei;
Un exemplu de model mai bun este dat in continuare:
ROBO observa ca (spre exemplu) aba si bbba sunt secvente de actiuni care conduc la repararea statiei si in modelul imbunatatit.
ROBO e convins ca poate gasi un model si mai bun. Acesta este cel din figura urmatoare:
ROBO nu poate gasi un model mai bun decat acesta din urma - unul cu numar de stari mai mic decat 3.
Pentru un model oarecare M, ROBO cauta numarul de stari al modelului cel mai bun - adica numarul minim de stari cu care putem reprezenta M astfel incat exact aceleasi secvente de actiuni din M conduc la reparatia statiei si in modelul imbunatatit.
Modelele au urmatoarele proprietati:
* Starea initiala este intotdeauna etichetata cu "0"
* Pentru fiecare stare si actiune, gasim intotdeauna o stare urmatoare;
* Nu exista stari inaccesibile (stari in care nu putem ajunge prin nici o secventa de actiuni);
Date de intrare
Datele de intrare se citesc din fişierul robo.in.
Pe prima linie se află numărul de teste, T. După aceea, pentru fiecare test sunt citite următoarele informaţii:
* Pe prima linie: numarul de stari urmat de numarul de actiuni posibile
* Pe a doua linie: o secventa de numere ce reprezinta starile in care statia e reparata
* Pe fiecare linie urmatoare: un triplet de forma stare actiune stare_urmatoare, unde stare si stare_urmatoare sunt numere iar actiune este un caracter alfabetic.
Date de ieşire
În fişierul de ieşire robo.out se va afişa, pentru fiecare test, câte o linie la standard output, care contine numarul de stari al modelului cel mai bun.
Restricţii
- 1 ≤ T ≤ 10
- 1 ≤ numar de stari ≤ 5200
- 1 ≤ numar de actiuni ≤ 10
Exemplu
| robo.in | robo.out |
|---|---|
| 1 5 2 4 0 a 1 0 b 2 1 b 1 1 a 4 2 a 4 2 b 3 3 a 4 3 b 2 4 a 4 4 b 4 | 3 |
