== include(page="template/taskheader" task_id="robo") ==
Poveste şi cerinţă...
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:
!problema/robo?robo1.jpg!
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:
!problema/robo?robo2.jpg!
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:
!problema/robo?robo3.jpg!
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);
h2. Date de intrare
Fişierul de intrare $robo.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $robo.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 10$
* $1 ≤ numar de stari ≤ 5200$
* $1 ≤ numar de actiuni ≤ 10$
h2. Exemplu
table(example). |_. robo.in |_. robo.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="robo") ==
== include(page="template/taskfooter" task_id="robo") ==
