.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » plimbare

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
 .campion
plimbare


Timp maxim de executie/test:
0.2 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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.

Cerinta

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 plimbare.in sunt se vor gasi numerele naturale X Y Z, separate prin spatii.

Date de iesire

Prima linie a fisierului plimbare.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

0 <= 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=(AiX,AiY,AiZ)) este mai mic din punct de vedere lexicografic decat un alt traseu B=(B1, B2, ..., Bn) (Bi=(BiX, BiY, BiZ)) 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: (a) AX<BX sau (b) AX=BX si AY<BY sau (c) AX=BX si AY=BY si AZ<BZ

Exemple

plimbare.in

plimbare.out plimbare.in

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

Mircea Paşoi
Universitatea Bucuresti,Facultatea de Matematica si Informatica
mircea@infoarena.ro

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la .campion 2007: perechi, teanc, index, light, copaci, teren, pizza, grupe, cod, ecran, drum, soldati, factura, palma, decript, lbd, aven, cs, h, trenuri, sort, spam, complex, parent, holo, tren2, gray, siruri, arce, pasi, cifre, mgo, firma, joc, cartonase, vikingi, anagrame, balbe, vecini, balaur, tribile, conflicte, criptmat, mesaj, maxim, magic3, desen, cutie, patrate, party, vagoane, robot, astre, trains, numere2, friends, tricouri, furtuna, net, baby, scaune, 3d, axa, bile2, vmem, pahare, termen, sablon, zapada, cuvinte, excursie, hd, pajura, pc, sir, cadere, pioni
De acelaşi autor: copaci, ab2, cuvinte, pioni, reinvent, numere3, perm, criptare, sume, gramezi, nr2, rev, paintball, matricea, emax, turism, puncte1, casute, dep
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
Despre operaţii pe biţi: barfa, cod, gray, cartonase, excursie, xor, vector, ro, nrbinar, radio, chimie2, dans, metro, caini, newcomp, viteza, bcast, aritma, pereti, morse, paritate, gradina, xor2, game1, efect, gxor, lgdrum, qtri, patrate7, panda, cript
surse trimise | ajutor