Instalatorul Mario a plecat în căutarea prințesei Peach. Până a ajunge la Castelul lui Bowser, acolo unde era ținută prizonieră prințesa, Mario a adunat monede magice. Fiecare monedă, numerotată de la la are o anumită valoare, moneda având valoarea ().
Ajuns la Castel, Mario l-a întâlnit pe Bowser care era mândrul posesor a unei colecții impresionante de monede, numerotate de la la , moneda având o valoare ().
În confruntarea finală, Bowser îi oferă lui Mario, șansa de a o salva pe Peach doar dacă reușește să facă schimburile necesare între monedele lor, astfel încât cele mai mici monede să fie în posesia lui Mario și cele mai mari valori să fie în posesia lui Bowser. Numărul de schimburi trebuie să fie minim.
Cerință
Scrieți un program care să îi permită lui Mario să o salveze pe Peach.
Date de intrare
Fişierul de intrare mario.in
conţine pe prima linie numărul , reprezentând numărul de monede găsite de Mario, pe următoarea linie cele valori ale monedelor găsite de Mario, separate prin câte un spațiu. Pe a treia linie se află numărul , numărul monedelor lui Bowser, iar pe ultima linie, separate prin câte un spațiu, cele valori ale monedelor lui Bowser.
Date de ieșire
Pe prima linie a fișierului de ieşire mario.out
se va afișa numărul de schimbări între cele două mulțimi de monede. Următoarele linii conțin schimbările, pe fiecare linie aflându-se două valori naturale cu semnificația "moneda cu numărul de ordine dintre cele deținute de Mario se va schimba cu moneda cu numărul de ordine dintre cele deținute de Bowser".
Restricții și precizări
- Valorile din fiecare cutie sunt .
- Soluția nu este unică.
- Pentru determinarea corectă a lui se acordă din punctaj, iar pentru determinarea corectă a schimbărilor .
Exemplu
mario.in
6
3 1 7 4 6 2
2
4 5
mario.out
2
3 1
5 2
Explicație
Se vor face două schimburi de monede și anume moneda cu numărul de ordine dintre monedele lui Mario se va schimba cu moneda cu numărul de ordine dintre monedele lui Bowser, apoi moneda a -a se va schimba cu moneda a -a.
Se observă că și soluția de mai jos este corectă:
2
3 2
5 1