Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dicsi.in, dicsi.out | Sursă | FMI No Stress 2017 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Fmi No Stress 7 •fmins7 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dicsi
Toata lumea il stie pe celebrul personaj, Dicsi. Acesta tocmai a aflat ca are N copii (cu o fata speciala). Deoarece Dicsi este familist, acesta doreste sa isi cunoasca copii mai bine, insa acest lucru nu este foarte usor intrucat Dicsi are foarte multi copii ( N ≤ 100.000 ). Fiind un informatician inascut, Dicsi a luat 2 masuri:
- Toti copii au fost numerotati cu indici de la 1 la N
- Toti copii au fost colorati, fiecare cu cate o culoare.
Doi copii se considera ca seamana intre ei daca indicele unuia este divizor al indicelui celuilalt. Dicsi nu vrea sa coloreze doi copii care seamana intre ei cu aceeasi culoare deoarece dupa i-ar confunda. Ajutati-l pe Dicsi sa determine numarul minim de culori necesar sa isi coloreze copii, precum si o configuratie de colorare.
Date de intrare
Fişierul de intrare dicsi.in va contine un singur numar N, reprezentand numarul de copii.
Date de ieşire
Fişierul de ieşire dicsi.out va contine pe prima linie un numar X, reprezentand numarul minim de culori necesar. Pe linia a doua se vor afisa N numere naturale din intervalul [1,X], al i-ulea element reprezentand culoarea celui de al i-ulea copil. Daca exista mai multe solutii, puteti afisa oricare.
Restricţii
- 1 ≤ N ≤ 100.000
Exemplu
| dicsi.in | dicsi.out |
|---|---|
| 5 | 3 1 2 2 3 2 |
Explicaţie
...
