OJI 2026 · clasa 9 · subiect oficial · clasa a 9-a

collatz

citire/afișare: consolă (cin/cout, input/print)timp 0.2smemorie 256 MBsursă ≤ 64 KB25 testepunctaj maxim 100p

Collatz are $T$ vectori, fiecare vector $i$ ( $1 \le i \le T$ ) fiind format inițial din numerele naturale consecutive de la $S_i$ la $D_i$ . După părerea lui, un vector îngrijit are toate elementele egale cu $1$ . Deoarece lui Collatz îi plac vectorii îngrijiți, el își dorește ca toate elementele vectorilor să devină $1$ , așa că transformă pe rând vectorii, aplicând pentru fiecare un număr minim de operații. O operație constă din alegerea unui element al vectorului și apoi:

dacă elementul este par, atunci valoarea lui se înjumătățește;
dacă elementul este impar, având inițial valoarea $x$ , atunci valoarea lui devine $2 \cdot x + 2$ .

Cerință

Pentru fiecare dintre cei $T$ vectori, determinați numărul minim de operații prin care poate deveni îngrijit.

Subiect oficial SEPI · OJI 2026. Adaptare citire/afișare la consolă.

Date de intrare

Intrarea standard conține pe prima linie numărul $T$ , cu semnificația din enunț, iar pe fiecare din următoarele $T$ linii se află câte două numere $S_i$ și $D_i$ , separate prin câte un spațiu, cu semnificația din enunț pentru fiecare vector $i$ .

Date de ieșire

Ieșirea standard conține $T$ numere, fiecare pe câte o linie, reprezentând numărul minim cerut pentru fiecare dintre cei $T$ vectori în ordine.

Restricții

$1 \le T \le 1 \ 000$ , număr natural;
$1 \le S_i \le D_i \le 10^{16}$ și $S_i, D_i$ sunt numere naturale, pentru orice $1 \le i \le T$ .

#	Punctaj	Restricții
1	63	$D_i \le 1 \ 000$
2	16	$D_i \le 10^6$
3	12	$D_i \le 10^7$
4	9	fără alte restricții

Exemplul 1

Date de intrare (tastatură)

Date de ieșire (ecran)

1
9
7

Desen

Explicație

Primul vector: Vectorul inițial este $[2]$ . Este nevoie de o singură operație pentru a-l transforma pe $[2]$ în $[1]$ .

Al doilea vector: Vectorul inițial este $[4, 5]$ . O succesiune posibilă de $9$ operații pentru a transforma vectorul în $[1, 1]$ este următoarea:

$[4, 5] \rightarrow [4, 12]$
$[4, 12] \rightarrow [4, 6]$
$[4, 6] \rightarrow [4, 3]$
$[4, 3] \rightarrow [4, 8]$
$[4, 8] \rightarrow [4, 4]$
$[4, 4] \rightarrow [4, 2]$
$[4, 2] \rightarrow [4, 1]$
$[4, 1] \rightarrow [2, 1]$
$[2, 1] \rightarrow [1, 1]$

Al treilea vector: vectorul inițial este $[1, 2, 3, 4]$ . O succesiune posibilă de $7$ operații pentru a transforma vectorul în $[1, 1, 1, 1]$ este:

$[1, 2, 3, 4] \rightarrow [1, 2, 3, 2]$
$[1, 2, 3, 2] \rightarrow [1, 2, 3, 1]$
$[1, 2, 3, 1] \rightarrow [1, 2, 8, 1]$
$[1, 2, 8, 1] \rightarrow [1, 1, 8, 1]$
$[1, 1, 8, 1] \rightarrow [1, 1, 4, 1]$
$[1, 1, 4, 1] \rightarrow [1, 1, 2, 1]$
$[1, 1, 2, 1] \rightarrow [1, 1, 1, 1]$ .

collatz

citire/afișare: consolă (cin/cout, input/print)timp 0.2smemorie 256 MBsursă ≤ 64 KB25 testepunctaj maxim 100p

Mergi la editor

dacă elementul este par, atunci valoarea lui se înjumătățește;
dacă elementul este impar, având inițial valoarea $x$ , atunci valoarea lui devine $2 \cdot x + 2$ .

Cerință

Pentru fiecare dintre cei $T$ vectori, determinați numărul minim de operații prin care poate deveni îngrijit.

Subiect oficial SEPI · OJI 2026. Adaptare citire/afișare la consolă.

Restricții

$1 \le T \le 1 \ 000$ , număr natural;
$1 \le S_i \le D_i \le 10^{16}$ și $S_i, D_i$ sunt numere naturale, pentru orice $1 \le i \le T$ .

#	Punctaj	Restricții
1	63	$D_i \le 1 \ 000$
2	16	$D_i \le 10^6$
3	12	$D_i \le 10^7$
4	9	fără alte restricții

Exemplul 1

Date de intrare (tastatură)

Date de ieșire (ecran)

1
9
7

Desen

Explicație

Primul vector: Vectorul inițial este $[2]$ . Este nevoie de o singură operație pentru a-l transforma pe $[2]$ în $[1]$ .

Al doilea vector: Vectorul inițial este $[4, 5]$ . O succesiune posibilă de $9$ operații pentru a transforma vectorul în $[1, 1]$ este următoarea:

$[4, 5] \rightarrow [4, 12]$
$[4, 12] \rightarrow [4, 6]$
$[4, 6] \rightarrow [4, 3]$
$[4, 3] \rightarrow [4, 8]$
$[4, 8] \rightarrow [4, 4]$
$[4, 4] \rightarrow [4, 2]$
$[4, 2] \rightarrow [4, 1]$
$[4, 1] \rightarrow [2, 1]$
$[2, 1] \rightarrow [1, 1]$

Al treilea vector: vectorul inițial este $[1, 2, 3, 4]$ . O succesiune posibilă de $7$ operații pentru a transforma vectorul în $[1, 1, 1, 1]$ este:

$[1, 2, 3, 4] \rightarrow [1, 2, 3, 2]$
$[1, 2, 3, 2] \rightarrow [1, 2, 3, 1]$
$[1, 2, 3, 1] \rightarrow [1, 2, 8, 1]$
$[1, 2, 8, 1] \rightarrow [1, 1, 8, 1]$
$[1, 1, 8, 1] \rightarrow [1, 1, 4, 1]$
$[1, 1, 4, 1] \rightarrow [1, 1, 2, 1]$
$[1, 1, 2, 1] \rightarrow [1, 1, 1, 1]$ .