Pls Traian intră în concurs | desen

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s Memory limit: 8MB Input: desen.in Output: desen.out

La ora de desen, Gigel a primit ca temă un desen care să fie realizat după următorul algoritm:
Pas 11: se desenează un triunghi, numerotat cu 11, ca în Figura 11;
Pas 22: se împarte triunghiul 11 în trei poligoane (un dreptunghi și două triunghiuri numerotate cu 22 și 33) trasând două segmente ca în Figura 22;
Pas 33: fiecare triunghi dintre cele două obținute la Pas 22, 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 33;
Pas 44: fiecare triunghi dintre cele patru obținute la Pas 33, se împarte în câte un dreptunghi și câte două triunghiuri (numerotate cu 88, 99, 1010, 1111, 1212, 1313, 1414, 1515) trasând câte două segmente ca în Figura 44;
\dots
Pas NN: fiecare triunghi dintre triunghiurile obținute la Pas N1N-1, se împarte în câte un dreptunghi și câte două triunghiuri trasând câte două segmente. Dacă valoarea lui KK este ultimul număr folosit pentru numerotarea triunghiurilor obținute la Pas N1N-1, atunci triunghiurile rezultate la Pas NN vor fi numerotate cu numerele naturale distincte consecutive K+1K+1, K+2K+2, K+3K+3, \dots etc.

Cerință

Scrieţi un program care să citească numărul natural K și să determine:

  1. cel mai mic număr XX și cel mai mare număr YY dintre numerele folosite pentru numerotarea triunghiurilor obținute la pasul în care este obținut și triunghiul numerotat cu KK;
  2. numerele triunghiurilor care au fost împărțite conform algoritmului din enunț astfel încât să fie obținut triunghiul numerotat cu KK.

Date de intrare

Dacă C=1C=1, atunci prima linie a fişierului de ieşire desen.out conţine cele două numere naturale XX și YY, separate printr-un singur spațiu, reprezentând răspunsul la cerința 11 a problemei.
Dacă C=2C=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 22 a problemei.

Date de ieșire

Pe prima linie a fișierului de ieșire desen.out se va găsi un singur număr întreg, suma celor două numere.

Restricții și precizări

  • 2K9 223 372 036 854 775 807 (=2631)2 \leq K \leq 9 \ 223 \ 372 \ 036 \ 854 \ 775 \ 807 \ (=2^{63}-1);
  • Doar triunghiurile sunt numerotate;
  • Pentru rezolvarea corectă a cerinţei 11 se acordă 4040 de puncte;
  • Pentru rezolvarea corectă a cerinței 22 se acordă 6060 de puncte.

Exemplul 1

desen.in

1
13

desen.out

8 15

Explicație

Cerința este 11, K=13K=13. Așa cum arată în Figura 4, la Pas 4 se obțin triunghiurile numerotate cu X = 8\textbf{X =} \ 8, 99, 1010, 1111, 1212, 1313, 1414, Y = 15\textbf{Y =} \ 15.

Exemplul 2

desen.in

2
13

desen.out

1 3 6

Explicație

Cerința este 22, K=13K=13. Așa cum arată Figura 4, triunghiul numerotat cu K=13K=13 se obține din triunghiul 66. Triunghiul 66 este obținut din triunghiul 33 care este obținut din triunghiul 11.

Log in or sign up to be able to send submissions!