| 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. Daca vreti sa vi-l imaginati arata ca o roata de bicicleta in care muchiile grafului sunt spitele bicicletei.
Cerinta
Se da un graf stea cu N noduri. N - 2 noduri din cele N au asociata o valoare unică de la 1 la N - 2, iar restul de 2 sunt libere. O mutare constă în selectarea unui 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 numerele asociate fiecarui nod din graf, incepand cu nodul 1 (centrul) si pana la n. Daca un nod este initial gol, se considera ca numarul asociat acestuia este 0.
A treia linie contine tot n numere: pentru fiecare nod, numarul ce trebuie sa fie in el in urma mutarilor, sau 0 daca nodul trebuie sa fie gol.
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. Nodurile x si y trebuie sa fie vecine, nodul x trebuie sa contina un numar iar nodul y sa fie gol ca mutarea sa fie valida.
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
