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.
Cerinţă
Ajutaţi căutătorii de comori să treacă de ultima probă şi ei vă vor da o parte din comoara găsită.
Date de intrare
Fişierul de intrare
comoara2.in are două linii. Pe prima linie se află 3 numere naturale separate prin câte un spaţiu
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.
Date de ieşire
Fişierul de ieşire
comoara2.out 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 ».
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
• Pentru testele folosite la evaluare există soluţie.
Exemple
comoara2.in | comoara2.out | Explicaţii |
3 5 8
4
| 6
3 2
2 3
1 3
2 3
3 2
2 1
| Î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
|