Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-08-08 16:57:22.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:cinema.in, cinema.outSursăLista lui Francu
AutorCristian CadarAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cinema

Un grup de N prieteni se duc la cinema. Fiecare dintre ei si-a cumparat bilet separat, insa conform intelegerii initiale toti si-au luat bilete in acelasi rand. Ajungand dupa inceputul filmului, ei se aseaza la intamplare pe acel rand. Fiecare dintre cei N prieteni considera ca locul de pe biletul sau este cel mai bun, asa ca fiecare doreste sa ajunga pe locul sau. Pentru a nu deranja prea tare restul spectatorilor ei se hotarasc ca in fiecare minut, mai multe perechi de persoane sa-si schimbe locurile intre ele. La fiecare minut, numarul de schimbari de locuri poate fi oricat de mare, insa o persoana nu poate participa decat la o singura astfel de schimbare. Pentru simplitate, consideram ca persoana 1 are biletul cu locul 1, persoana 2 are biletul cu locul 2, si asa mai departe, persoana N are biletul cu locul N.

Cerinta

Aflati numarul minim de minute necesare pentru ca fiecare persoana sa ajunga pe locul sau.

Date de intrare

Pe prima linie a fisierului cinema.in este scris numarul de prieteni N. Pe urmatoarea linie se afla N numere reprezentand locul pe care s-a asezat initial fiecare prieten.

Date de iesire

Prima linie a fisierului cinema.out va contine numarul minim M de minute necesare pentru ca fiecare persoana sa ajunga pe locul sau. Urmeaza M linii cu urmatoarea structura: numarul R de mutari care sunt executate la minutul respectiv, iar apoi R perechi de numere i j, separate printr-un spatiu, avand semnificatia ca in minutul respectiv persoana i isi schimba locul cu persoana j.

Restrictii

  • 2 ≤ N ≤ 1000
  • Evaluarea se face pe 10 teste. Punctajul primit pentru fiecare test care ordoneaza corect este
    [(M Ok /M ultilizator)2 * 10]

Exemplu

cinema.incinema.out
3
3 1 2
2
1 1 2
1 2 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content