Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dubi.in, dubi.out | Sursă | Junior Challenge 2015 |
| Autor | Andrei Constantinescu, Costin Oncescu | Adăugată de |  JuniorChallenge2016 •JuniorChallenge2015 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Funcţia Dubioasă
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).
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.
Date de intrare
Fişierul de intrare dubi.în conţine pe prima linie numărul N de oraşe.
Date de ieşire
În fişierul de ieşire dubi.out se va afişa pe prima linie numărul K de judeţe din împărţire. Liniile de la 2 la K + 1 vor reprezenta descrierea fiecărui judeţe în parte, astfel: pe linia i + 1 se afişează mai întâi numărul de oraşe din judeţul i şi apoi oraşele în ordine crescătoare, separate prin câte un spaţiu.
Restricţii
- 1 ≤ N ≤ 2 * 105
- Atentie! Volum mare de date de intrare, va recomandăm să optimizaţi citirea folosindu-va de acest cod.
- Subtask 1 (20 puncte): 1 ≤ N ≤ 20
- Subtask 2 (20 puncte): 1 ≤ N ≤ 212 şi N este o putere a lui 2
- Subtask 3 (60 puncte): Restricţii iniţiale
Exemplu
| dubi.in | dubi.out |
|---|---|
| 4 | 3 2 1 3 1 2 1 4 |
Explicaţie
În total vor fi 3 judeţe (două formate doar din câte un oraş, respectiv 2 şi 4, singurul drum relevant existând în judeţul format din oraşele 1 şi 3). Drumul 1 3 există deoarece 1 ≤ 1 xor 3 = 2 ≤ 3.
