Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | starcity.in, starcity.out | Sursă | Algoritmiada 2016 Runda 1 Juniori |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
StarCity
Se da un graf stea cu N noduri. N - 2 noduri din cele N au asociata o valoare distinca de la 1 la N - 2, iar restul de 2 sunt libere. O mutare consta din selectarea unei nod ocupat de o valoare si mutarea acestei valori intr-un nod vecin liber.
Un graf stea este un graf in care unul dintre noduri(numit centrul grafului) este conectat printr-o muchie cu fiecare dintre celelalte noduri, iar fiecare nod din cele N - 1 ramase este conectat doar cu centrul grafului.
Cerinta
Dandu-se o configuratie initiala si o configuratie finala, sa se spuna numarul minim de pasi si o secventa de mutari astfel incat sa se ajunga din configuratia initiala in cea finala.
Date de intrare
Fişierul de intrare starcity.in contine 3 linii.
Pe prima linie va fi dat numarul natural N.
A doua linie contine configuratia initiala.
A treia linie contine configuratia la care trebuie sa se ajunga.
Date de ieşire
În fişierul de ieşire starcity.out se va afisa pe prima line numarul minim de mutari K. Pe pe fiecare din urmatoarele K linii se vor afisa doua numere naturale x si y care reprezinta mutarea valorii din nodul x in nodul y.
Restricţii
- 3 ≤ N ≤ 500.000
Exemplu
| starcity.in | starcity.out |
|---|---|
| 4 0 0 1 2 0 0 2 1 | 6 3 1 1 2` 4 1 1 3 2 1 1 4 |
Explicaţie
Graful stea va trece prin urmatoarele stari:
$0 0 1 2
1 0 0 2
0 1 0 2
2 1 0 0
0 1 2 0
1 0 2 0
0 0 2 1$
