Functia Dubioasa

Funcţia Dubioasă

== include(page="template/taskheader" task_id="dubi") ==

Chappie, roboţelul, a primit o sarcina nouă de la tatăl sau, Ninja, şi anume împărţirea în mai multe judeţe a unei ţări pe care tocmai au pus stăpânire. Ţară asediată de Ninja conţine $N$ oraşe numerotate de la $1$ la $N$. Ninja doreşte o împărţire în număr minim de judeţe astfel încât oricare două oraşe dintr-un judeţ să aibă un drum direct între ele. În împărţirea sa Chappie trebuie să aibă grijă ca fiecare oraş să aparţină exact unui singur judeţ. Unchiul său, Amerika, este responsabil de construirea drumurilor. Acesta construieşte un drum direct între oraşele numerotate $X$ şi $Y$ dacă şi numai dacă $min (X, Y) ≤ X xor Y ≤ max (X, Y)$ (cu alte cuvinte, dacă numărul $X xor Y$ se află între X şi Y).

Chappie, roboţelul, a primit o sarcină nouă de la tatăl său, Ninja, şi anume împărţirea în mai multe judeţe a unei ţări pe care tocmai au pus stăpânire. Ţara asediată de Ninja conţine $N$ oraşe numerotate de la $1$ la $N$. Ninja doreşte o împărţire în număr minim de judeţe astfel încât oricare două oraşe dintr-un judeţ să aibă un drum direct între ele. În împărţirea sa Chappie trebuie să aibă grijă ca fiecare oraş să aparţină exact unui singur judeţ. Unchiul său, Amerika, este responsabil de construirea drumurilor. Acesta construieşte un drum direct între oraşele numerotate $X$ şi $Y$ dacă şi numai dacă $min (X, Y) ≤ X xor Y ≤ max (X, Y)$ (cu alte cuvinte, dacă numărul $X xor Y$ se află între X şi Y).

Cum Chappie este ocupat să "adoarmă" oamenii care au furat de la tatăl lui, el va cere ajutorul în schimbul căruia veţi primi 100 de puncte.

* $1 ≤ N ≤ 2 * 10^5^$

* **Subtask 1 (20 puncte)**: $1 ≤ N ≤ 20$
* **Subtask 2 (20 puncte)**: $1 ≤ N ≤ 2^12^ şi N este o putere a lui 2$
* **Subtask 3 (60 puncte)**: Restricţii iniţiale
 

* **Observaţie:** operaţia "xor pe biţi":https://ro.wikipedia.org/wiki/Disjunc%C8%9Bie_exclusiv%C4%83 reprezintă adunarea bit cu bit fără transport (de exemplu $1100 xor 1010 = 0110$).

* **Atentie!** Fiecare subtask are testele grupate!
* **Subtask 1 (20 puncte)**: $1 ≤ N ≤ 20$ (Feedback testul 2)
* **Subtask 2 (20 puncte)**: $1 ≤ N ≤ 2^12^ şi N este o putere a lui 2$ (Feedback testul 4)
* **Subtask 3 (60 puncte)**: Restricţii iniţiale (Feedback testul 9)
 

h2. Exemplu
table(example). |_. dubi.in |_. dubi.out |