Problema pe care o trimit astazi a fost propusa de mine la barajele pentru
olimpiada internationala, ce au avut loc la Sinaia la sfarsitul lunii
septembrie. Imi cer scuze membrilor lotului, care cunosc deja problema.
Deadline-ul acestei probleme este asa cum mi s-a cerut, ceva mai
tarziu, luni 8 noiembrie, pentru a avea timp sa va "reacomodati" cu scoala.
Oricum, sper ca in viitorul apropiat propunerea problemelor pe lista sa
se modifice radical (in bine), dar pastrez surpriza pana la posibila
ei finalizare.
Mult succes in continuare !
Cristian Cadar
---------------------------------
| PROBLEMA 34: Secventa |
| PUNCTAJ: 100 Dexteri |
| DEADLINE: Luni, 8 Noiembrie |
| TIMP DE IMPLEMENTARE: 60 minute |
| TIMP DE EXECUTIE: 1 sec./test |
---------------------------------
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 randul 17. Ajungand dupa inceputul filmului, ei se
aseaza la intamplare pe randul 17. 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.
Aflati numarul minim de minute necesare pentru ca fiecare persoana
sa ajunga pe locul sau.
Pentru simplificare, 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.
Date de intrare
Datele de intrare se citesc din fisierul CINEMA.IN. Pe prima linie
este scris numarul n (n<=1000) de prieteni care merg la cinema. Pe
fiecare din urmatoarele n linii se afla cate un numar, reprezentand
locul pe care prietenii s-au asezat initial.
Date de iesire
Datele de iesire se scriu in fisierul CINEMA.OUT. Prima linie
a acestui fisier va contine numarul minim M de minute necesare pentru
ca fiecare persoana sa ajunga pe locul sau. Urmeaza M blocuri cu
urmatoarea structura:
- prima linie a blocului contine numarul R de mutari care sunt
executate la minutul respectiv;
- urmatoarele R linii contin perechi de numere (i j), separate
printr-un spatiu, avand semnificatia: in minutul respectiv,
persoana i isi schimba locul cu persoana j.
Exemplu
CINEMA.IN CINEMA.OUT
3 2
3 1
1 1 2
2 1
2 3
|
|
