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, robotelul, a primit o sarcina noua de la tatal sau, Ninja, si anume, impartirea in mai multe judete a unei tari pe care tocmai au pus stapanire. Tara asediata de Ninja contine N orase numerotate de la 1 la N. Ninja doreste o impartire in numar minim de judete astfel incat oricare doua orase dintr-un judet sa aiba un drum direct intre ele. In impartirea sa, Chappie trebuie sa atribuie fiecarui oras exact un judet din care face parte. Unchiul sau, Amerika, este responsabil de construirea drumurilor. Acesta construieste un drum direct intre orasele numerotate X si Y daca si numai daca X xor Y >= min (X, Y) si X xor Y <= max (X, Y) (cu alte cuvinte, daca numarul X xor Y se afla intre X si Y).
Cum Chappie este ocupat sa "adoarma" oamenii care au furat de la tatal lui, el va cere ajutorul in schimbul caruia va va da 100 de puncte.
Date de intrare
Fişierul de intrare dubi.in contine pe prima linie numarul N de orase.
Date de ieşire
În fişierul de ieşire dubi.out se va afisa pe prima linie numarul de K judete din impartire. Liniile de la 2 la K + 1 vor reprezenta descrierea fiecarui judete in parte, astfel: pe linia i + 1, se afiseaza mai intai numarul de orase din judetul i si apoi orasele in ordine crescatoare, separate prin cate un spatiu.
Restricţii
- 1 ≤ N ≤ 200000
- Pentru teste in valoare de 20% din punctaj, 1 ≤ N ≤ 20
- Pentru alte teste in valoare de 20% din punctaj, 1 ≤ N ≤ 2 ^ 15 si N este o putere a lui 2
Exemplu
| dubi.in | dubi.out |
|---|---|
| 4 | 3 2 1 3 1 2 1 4 |
Explicaţie
...
