Fişierul intrare/ieşire:plimbare2.in, plimbare2.outSursă.campion 2007-2008, Runda 8
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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 (x1, y1, z1) el va merge doar intr-o pozitie de forma (x1±2n, y1±2n, z1±2n) 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 Pmin reprezentand numarul minim de pozitii. Urmatoarele Pmin linii vor contine cate trei numere intregi pe o linie, reprezentand pozitiile (X, Y, Z) prin care trece Zaharel.

Restrictii

  • 1 ≤ X, Y, Z ≤ 1018
  • 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=(A1, A2..., An) (Ai=(Ai,X,Ai,Y,Ai,Z)) este mai mic din punct de vedere lexicografic decat un alt traseu B=(B1, B2..., Bn) (Bi=(Bi,X,Bi,Y,Bi,Z)) daca exista o pozitie 1≤i≤N astfel incat A1=B1, A2=B2, ..., Ai-1=Bi-1 si Ai<Bi.
  • O pozitie A=(AX, AY, AZ) este mai mica din punct de vedere lexicografic decat o alta pozitie B=(BX, BY, BZ) daca:
    • AX<BX sau
    • AX=BX si AY<BY sau
    • AX=BX si AY=BY si AZ<BZ

Exemplu

plimbare2.inplimbare2.out
16 16 16
2
0 0 0
16 16 16
123 213 321
10
0 0 0
-128 -128 128
-192 -64 64
-194 -62 62
-193 -63 61
-189 -67 57
-181 -59 49
-165 -75 33
-133 -43 65
123 213 321
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content