| Fişierul intrare/ieşire: | egipt.in, egipt.out | Sursă | Grigore Moisil 2010, Clasa a 10-a |
| Autor | Clara Ionescu | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | egipt.out |
|---|---|
| 5 3 2 1 1 2 | 3 2 3 1 4 4 5 |
