egipt

Egipt

== include(page="template/taskheader" task_id="egipt") ==

Poveste şi cerinţă...

Î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.
 
h3. 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!

h2. Date de intrare

Fişierul de intrare $egipt.in$ ...

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$.

h2. Date de ieşire

În fişierul de ieşire $egipt.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 10 000$

h2. Exemplu
table(example). |_. egipt.in |_. egipt.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
3
2
1
1
2
| 3
2 3
1 4
4 5

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="egipt") ==

4728