La ora de desen, Gigel a primit ca temă un desen care să fie realizat după următorul algoritm:
Pas 1: se desenează un triunghi, numerotat cu 1, ca în Figura 1;
Pas 2: se împarte triunghiul 1 în trei poligoane (un dreptunghi și două triunghiuri numerotate cu 2 și 3) trasând două segmente ca în Figura 2;
Pas 3: fiecare triunghi dintre cele două obținute la Pas 2, se împarte în câte un dreptunghi și câte două triunghiuri (numerotate cu 4,5,6,7) trasând câte două segmente ca în Figura 3;
Pas 4: fiecare triunghi dintre cele patru obținute la Pas 3, se împarte în câte un dreptunghi și câte două triunghiuri (numerotate cu 8,9,10, 11,12,13,14,15) trasând câte două segmente ca în Figura 4 ;
*Pas 1*: se desenează un triunghi, numerotat cu 1, ca în *Figura 1*;
*Pas 2*: se împarte triunghiul 1 în trei poligoane (un dreptunghi și două triunghiuri numerotate cu 2 și 3) trasând două segmente ca în *Figura 2*;
*Pas 3*: fiecare triunghi dintre cele două obținute la *Pas 2*, se împarte în câte un dreptunghi și câte două triunghiuri (numerotate cu 4,5,6,7) trasând câte două segmente ca în *Figura 3*;
*Pas 4*: fiecare triunghi dintre cele patru obținute la *Pas 3*, se împarte în câte un dreptunghi și câte două triunghiuri (numerotate cu 8,9,10, 11,12,13,14,15) trasând câte două segmente ca în *Figura 4*;
.......
Pas N: fiecare triunghi dintre triunghiurile obținute la Pas N-1, se împarte în câte un dreptunghi și câte două triunghiuri trasând câte două segmente.
*Pas N*: fiecare triunghi dintre triunghiurile obținute la *Pas N-1*, se împarte în câte un dreptunghi și câte două triunghiuri trasând câte două segmente.
Dacă valoarea lui K este ultimul număr folosit pentru numerotarea triunghiurilor obținute la Pas N-1, atunci triunghiurile rezultate la Pas N vor fi numerotate cu numerele naturale distincte consecutive K+1, K+2, K+3,... etc.
Dacă valoarea lui *K* este ultimul număr folosit pentru numerotarea triunghiurilor obținute la *Pas N-1*, atunci triunghiurile rezultate la *Pas N* vor fi numerotate cu numerele naturale distincte consecutive *K*+1, *K*+2, *K*+3, ..., etc.
h2. Cerințe
Scrieți un program care să citească numărul natural K și să determine:
Scrieți un program care să citească numărul natural *K* și să determine:
# cel mai mic număr X și cel mai mare număr Y dintre numerele folosite pentru numerotarea triunghiurilor obținute la pasul în care este obținut și triunghiul numerotat cu K;
# numerele triunghiurilor care au fost împărțite conform algoritmului din enunț astfel încât să fie obținut triunghiul numerotat cu K.
# cel mai mic număr *X* și cel mai mare număr *Y* dintre numerele folosite pentru numerotarea triunghiurilor obținute la pasul în care este obținut și triunghiul numerotat cu *K*;
# numerele triunghiurilor care au fost împărțite conform algoritmului din enunț astfel încât să fie obținut triunghiul numerotat cu *K*.
h2. Date de intrare
Fișierul de intrare $desen.in$ conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). Fișierul conține pe a doua linie numărul natural K.
Fișierul de intrare $desen.in$ conține pe prima linie un număr natural *C* reprezentând cerința din problemă care trebuie rezolvată (1 sau 2). Fișierul conține pe a doua linie numărul natural *K*.
h2. Date de ieșire
Dacă C=1, atunci prima linie a fișierului de ieșire $desen.out$ conține cele două numere naturale X și Y, separate printr-un singur spațiu, reprezentând răspunsul la cerința 1 a problemei.
Dacă *C*=1, atunci prima linie a fișierului de ieșire $desen.out$ conține cele două numere naturale *X* și *Y*, separate printr-un singur spațiu, reprezentând răspunsul la cerința 1 a problemei.
Dacă C=2, atunci prima linie a fișierului de ieșire desen.out conține un șir de numere naturale ordonate crescător, separate prin câte un spațiu, reprezentând răspunsul la cerința 2 a problemei.
Dacă *C*=2, atunci prima linie a fișierului de ieșire $desen.out$ conține un șir de numere naturale ordonate crescător, separate prin câte un spațiu, reprezentând răspunsul la cerința 2 a problemei.
h2. Restricții
* 2 ≤ K ≤ 9223372036854775807 (=2[^63^]-1)
* 2 ≤ *K* ≤ 9223372036854775807 (=2[^63^]-1)
* doar triunghiurile sunt numerotate
* pentru rezolvarea corectă a cerinței 1 se acordă 40 de puncte
* pentru rezolvarea corectă a cerinței 2 se acordă 60 de puncte.
| 1
13
| 8 15
| Cerința este 1, K=13. Așa cum arată în Figura 4, la Pas 4 se obțin triunghiurile
numerotate cu X=8, 9, 10, 11, 12, 13, 14, Y=15.
| Cerința este 1, *K*=13. Așa cum arată în Figura 4, la Pas 4 se obțin triunghiurile
numerotate cu *X*=8, 9, 10, 11, 12, 13, 14, *Y*=15.
|
| 2
13
| 1 3 6
| Cerința este 2, K=13. Așa cum arată Figura 4, triunghiul numerotat cu K=13 se
| Cerința este 2, *K*=13. Așa cum arată Figura 4, triunghiul numerotat cu *K*=13 se
obține din triunghiul 6. Triunghiul 6 este obținut din triunghiul 3 care este obținut din
triunghiul 1.
|
