Fişierul intrare/ieşire:egipt.in, egipt.outSursăGrigore Moisil 2010, Clasa a 10-a
AutorClara IonescuAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Egipt

În Egiptul antic se va construi o piramidă. Pe terenul respectiv au fost cărate multe blocuri de piatră şi aşezate de-a lungul unei linii drepte. Blocurile de piatră au fost prelucrate în prealabil, astfel încât acestea au trei dimensiuni diferite. Constructorul şef al faraonului vrea să micşoreze efortul de a construi piramida şi astfel el ar vrea să aranjeze blocurile de piatră în ordine crescătoare după mărime.

Cerinţă

Determinaţi numărul minim de interschimbări de blocuri de piatră pe care sclavii faraonului va trebui să le efectueze în scopul aranjării acestora în ordine crescătoare. Stabiliţi şi numerele de ordine din configuraţia iniţială ale blocurilor de piatră care se vor interschimba!

Date de intrare

Fişierul de intrare egipt.in conţine pe prima linie numărul natural n, reprezentând numărul blocurilor de piatră. Pe următoarele n linii se află câte un număr natural, reprezentând tipul blocului de piatră. Acestea fiind de trei dimensiuni, tipul va fi 1, 2 sau 3.

Date de ieşire

În fişierul de ieşire egipt.out se va scrie pe prima linie un număr natural m, reprezentând numărul interschimbărilor necesare. Pe fiecare dintre următoarele m linii se va descrie câte o interschimbare, necesară de realizat pentru a obţine şirul de blocuri de piatră ordonat în felul următor: fiecare linie va conţine două numere naturale i j, având semnificaţia că se va interschimba blocul de pe poziţia i cu blocul de pe poziţia j.

Restricţii

  • 1 ≤ n ≤ 10 000

Exemplu

egipt.inegipt.out
5
3
2
1
1
2
3
2 3
1 4
4 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content