== include(page="template/taskheader" task_id="comoara") ==
Poveste şi cerinţă...
Până acum, pentru a găsi o comoară, un căutător trebuia sa treacă de diferite teste: trebuie să scape de bolovani uriaşi, de balauri, de săgeţi otrăvite. Comoara din insula piraţilor este mai specială, deoarece căpitanul care a ascuns-o a dorit să se asigure ca doar cineva care este perspicace va reuşi să ajungă la ea. Astfel, el a introdus o ultimă probă de perspicacitate, care se găseşte chiar în faţa intrării la comoară. Această ultimă probă este proba vaselor.
Căutătorii au la dispoziţie trei vase. Vasul 1 are capacitatea $A$, vasul 2 are capacitatea $B$, iar vasul 3 are capacitatea $C$. Capacităţile celor vase îndeplinesc relaţiile: $A<B<C$ şi $A+B=C$.
La începutul probei, $C$ este întotdeauna plin, iar $A$ şi $B$ goale. Pentru a trece cu succes de această probă şi a ajunge la comoară, căutătorii trebuie să facă în aşa fel încât să rămână în oricare dintre vase $M$ litri de apă.
Pentru aceasta ei pot efectua una sau mai multe mutări. O mutare din vasul $x$ în vasul $y$ constă din turnarea conţinutului vasului $x$ în vasul $y$ până când vasul $x$ se goleşte sau vasul $y$ se umple.
Ajutaţi căutătorii de comori să treacă de ultima probă şi ei vă vor da o parte din comoara găsită.
h2. Date de intrare
Fişierul de intrare $comoara.in$ ...
Fişierul de intrare are două linii. Pe prima linie se află 3 numere naturale separate prin câte un spaţu $A$ $B$ $C$, având semnificaţia din enunţ. Pe a doua linie se găseşte un număr natural $M$ reprezentând numărul de litri de apă ce trebuie să rămână într-un vas pentru a trece proba.
h2. Date de ieşire
În fişierul de ieşire $comoara.out$ ...
Fişierul de ieşire va conţine pe prima linie un număr natural $N$, reprezentând numărul de mutări efectuate.
Pe următoarele $N$ linii vor fi descrise cele $N$ mutări, câte o mutare pe o linie. O mutare va fi descrisă ca o pereche x y de numere distincte din mulţimea {1, 2, 3}, cu semnificaţia « se toarnă apă din vasul $x$ în vasul $y$ ».
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 < A, B, C < 100 001$
* numărul de mutări nu trebuie să fie minim însă el nu trebuie să depăşească 200 000
* testele folosite vor avea soluţie
* nu se acord punctaje partiale
h2. Exemplu
table(example). |_. comoara.in |_. comoara.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 5 8
4
| 6
3 2
2 1
1 3
2 1
3 2
2 1
|
h3. Explicaţie
...
În cele 3 vase rămân următoarele cantităţi:
0 5 3
3 2 3
0 2 6
2 0 6
2 5 1
3 4 1
== include(page="template/taskfooter" task_id="comoara") ==
