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
Un graf stea este un graf in care unul dintre noduri (nodul 1, 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
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. Sa se determine numarul minim de mutari pentru a transforma graful initial intr-un alt graf dat.
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 ≤ 100.000
- Daca solutia data este valida, dar numarul de mutari nu este minim, se va acorda 40% din punctaj.
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
