Fișierul intrare/ieșire desen.in, desen.out Sursă ONI 2018 clasa a 5-a
Autor Daniela Tătaru Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.3 sec Limită de memorie 8192 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Desen (clasa a 5-a)

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

Cerințe

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

  1. 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;
  2. numerele triunghiurilor care au fost împărțite conform algoritmului din enunț astfel încât să fie obținut triunghiul numerotat cu K.

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.

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

Restricții

  • 2 ≤ K ≤ 9223372036854775807 (=263-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.

Exemplu

desen.in desen.out Explicație
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.
2
13
1 3 6
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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii