| 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
Ştiti cum plâng copiii mici? WEEEEEEE
Toata lumea îl ştie pe celebrul personaj, Dicsi. Acesta tocmai a aflat că are N copii (cu o fată specială). Deoarece Dicsi este un familist, acesta îşi doreşte să işi cunoască copiii mai bine, însă acest lucru nu este foarte uşor întrucât Dicsi are foarte mulţi copii ( N ≤ 100.000 ). Fiind un informatician înnăscut, Dicsi a luat 2 măsuri:
- Toţi copiii au fost numerotaţi cu indici distincţi de la 1 la N
- Fiecare copil a fost colorat cu câte o culoare.
Doi copii se consideră ca seamănă între ei dacă indicele unuia este divizor al indicelui celuilalt. Dicsi nu vrea să coloreze doi copii care seamănă între ei cu aceeaşi culoare deoarece după i-ar confunda. Ajutaţi-l pe Dicsi să determine numărul minim de culori necesar acestuia să îşi colorze copiii astfel încât să nu îi confunde, precum şi o colorare validă.
Date de intrare
Fişierul de intrare dicsi.in va conţine un singur număr natural N, reprezentând numărul de copii.
Date de ieşire
Fişierul de ieşire dicsi.out va conţine pe prima linie un număr X, reprezentând numărul minim de culori necesar. Pe linia a doua se vor afişa N numere naturale din intervalul [1...X], al i-lea element reprezentând culoarea celui de al i-lea copil. Dacă există mai multe soluţii, puteţi afişa oricare dintre acestea.
Restricţii
- 1 ≤ N ≤ 100.000
Exemplu
| dicsi.in | dicsi.out |
|---|---|
| 5 | 3 3 2 1 1 2 |
