plimbare2

Plimbare 2

== include(page="template/taskheader" task_id="plimbare2") ==

Poveste si cerinta...

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{~1~}, y{~1~}, z{~1~})$ el va merge doar intr-o pozitie de forma $(x{~1~}±2^n^, y{~1~}±2^n^, z{~1~}±2^n^)$ 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)$.

h2. Date de intrare

Fisierul de intrare $plimbare2.in$ ...

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

h2. Date de iesire

In fisierul de iesire $plimbare2.out$ ...

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.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ X, Y, Z ≤ 10^18^$
* 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{~1~}, A{~2~}..., 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{~1~}, B{~2~}..., B{~n~}) (B{~i~}=(B{~i,X~},B{~i,Y~},B{~i,Z~}))$ daca exista o pozitie $1&le;i&le;N$ astfel incat $A{~1~}=B{~1~}, A{~2~}=B{~2~}, ..., 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~}$

h2. Exemplu
table(example). |_. plimbare2.in |_. plimbare2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...

| 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 |

== include(page="template/taskfooter" task_id="plimbare2") ==

2659