Fişierul intrare/ieşire:	plimbare2.in, plimbare2.out	Sursă	.campion 2007-2008, Runda 8
Autor	Mircea Bogdan Pasoi	Adăugată de	Mircea Pasoi •domino
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Plimbare 2

Zaharel a iesit la o plimbare. El va merge de la punctul de coordonate (0, 0, 0) la punctul de coordonate (X, Y, Z). Se stie ca Zaharel merge mai ciudat: dintr-o pozitie (x₁, y₁, z₁) el va merge doar intr-o pozitie de forma (x₁±2ⁿ, y₁±2ⁿ, z₁±2ⁿ) unde n este un numar natural. In plus, plimbarea de astazi este mai speciala, in sensul ca Zaharel nu va folosi decat valori distincte pentru n. Dandu-se numerele X Y Z sa se determine un traseu cu numar minim de pozitii pentru ca Zaharel sa ajunga de la (0, 0, 0) la (X, Y, Z).

Date de intrare

Pe prima linie a fisierului de intrare plimbare2.in sunt se vor gasi numerele naturale X Y Z, separate prin spatii.

Date de iesire

Prima linie a fisierului plimbare2.out va contine un singur numar natural P_min reprezentand numarul minim de pozitii. Urmatoarele P_min linii vor contine cate trei numere intregi pe o linie, reprezentand pozitiile (X, Y, Z) prin care trece Zaharel.

Restrictii

• 1 ≤ X, Y, Z ≤ 10¹⁸
• Se garanteaza ca pentru datele de test exista solutie.
• Daca exista mai multe trasee cu numar minim de pasi se va afisa acela care este minim lexicografic. Spunem ca un traseu A=(A₁, A₂..., A_n) (A_i=(A_i,X,A_i,Y,A_i,Z)) este mai mic din punct de vedere lexicografic decat un alt traseu B=(B₁, B₂..., B_n) (B_i=(B_i,X,B_i,Y,B_i,Z)) daca exista o pozitie 1≤i≤N astfel incat A₁=B₁, A₂=B₂, ..., A_i-1=B_i-1 si A_i<B_i.
• O pozitie A=(A_X, A_Y, A_Z) este mai mica din punct de vedere lexicografic decat o alta pozitie B=(B_X, B_Y, B_Z) daca:
  • A_X<B_X sau
  • A_X=B_X si A_Y<B_Y sau
  • A_X=B_X si A_Y=B_Y si A_Z<B_Z

Exemplu

Cum se trimit solutii?