Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | culori.in, culori.out | Sursă | preONI 2007, Runda 2 |
| Autor | Adrian Vladu | Adăugată de |  Adrian Vladu •azotlichid |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 20096 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Vezi solutiile trimise | Statistici
Culori
Alice si Bob, doi renumiti montaniarzi care tocmai au iesit din sesiune, s-au hotarat sa isi petreaca vacanta in inima muntilor. Intr-o zi, explorand padurile din preajma, au descoperit o pestera despre care au presupus ca odinioara a apartinut unei colonii de maimute. Conform cunostintelor acumulate in domeniu, pestera este formata din N camere unite prin coridoare bidirectionale astfel incat intre oricare doua camere exista un singur drum. Mai mult, peretii fiecarei camere au fost vopsiti de catre maimute intr-o culoare notata cu un numar intreg intre 1 si N.
Temerarii nostri doresc sa reconstituie harta pesterii. Pentru aceasta ei procedeaza in felul urmator:
* initial Bob se afla in camera #1
* cand Bob intra intr-o camera isi noteaza culoarea camerei respective. Apoi isi alege cel mai din stanga coridor pe care nu l-a vizitat si intra in camera adiacenta (evident, nevizitata anterior). Daca nu exista
Bob intra in camera #1 si isi noteaza culoarea camerei respective. Apoi isi alege cel mai din stanga coridor pe care nu l-a vizitat, intra in noua camera, isi noteaza culoarea camerei respective
Date de intrare
...
Date de iesire
...
Restrictii
- 1 ≤ N ≤ 50.000
- 0 ≤ G ≤ 200.000
Exemple
| ghiozdan.in | ghiozdan.out |
|---|---|
| 3 9 2 2 4 | 8 3 2 2 4 |
| 6 24 19 7 7 7 7 2 | 23 4 2 7 7 7 |
