Fişierul intrare/ieşire:telefon2.in, telefon2.outSursăONI 2010 - Baraj
AutorAndrei Paul Puni, Clara IonescuAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Telefon2

Cei N elevi ai unei clase s-au hotărât să formeze un „telefon fără fir”. Pentru aceasta, elevii au fost numerotaţi de la 1 la N, apoi fiecare elev şi-a ales un singur coleg (îl vom numi vecin), singurul căruia el îi va putea transmite în mod direct mesajele primite. Telefonul fără fir funcţionează astfel:

  • iniţial un elev transmite un mesaj (evident, numai vecinului său);
  • fiecare elev care a primit (direct sau indirect) mesajul, transmite mesajul primit mai departe, vecinului său.

Telefonul fără fir funcţionează corect, dacă oricare elev ar iniţia transmiterea mesajului, acesta va ajunge la fiecare dintre cei N elevi (deci inclusiv înapoi la elevul care a iniţiat transmiterea mesajului). Elevii au observat că telefonul lor fără fir nu funcţionează corect. Pentru ca telefonul fără fir să funcţioneze corect, ei se gândesc să realizeze o succesiune de modificări. Printr-o modificare un elev îşi poate schimba vecinul ales.

Cerinta

Determinaţi o succesiune cu număr minim de modificări, în urmă cărora telefonul fără fir să funcţioneze corect.

Date de intrare

Prima linie a fişierului de intrare telefon2.in conţine numărul natural N, reprezentând numărul elevilor. Pe cea de a doua linie se află N numere naturale, separate prin câte un spaţiu; al i-lea număr reprezintă vecinul ales de copilul i (1 ≤ i ≤ N).

Date de ieşire

Pe prima linie a fişierului de ieşire telefon2.out se va scrie un număr natural k, reprezentând numărul minim de modificări necesare pentru ca telefonul fără fir să funcţioneze corect. Pe următoarele k linii se va scrie succesiunea modificărilor efectuate, câte o modificare pe o linie. O modificare este specificată prin două numere naturale separate prin spaţiu, c v, cu semnificaţia că elevul c îşi schimbă vecinul, noul său vecin fiind v.

Restricţii

  • 1 < N ≤ 100 000
  • Dacă există mai multe soluţii, puteţi afişa oricare dintre acestea.
  • Pentru 30% din teste se garantează că fiecare elev va fi ales ca vecin de către alt elev
  • Pentru alte 30% din teste există cel puţin un elev care va primi direct sau indirect mesajul transmis de către oricare elev, inclusiv el însuşi.
  • Pentru alte 20% din teste N ≤ 1000
  • Se vor acorda punctaje parţiale astfel:
    • 30% din punctajul pe fiecare test, reprezintă numărul minim de modificări
    • Restul de 70% pentru reconstituirea soluţiei

Exemplu

telefon2.intelefon2.out
10
6 9 2 7 3 1 9 3 7 9
5
2 4
6 10
8 5
9 1
10 8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content