Fişierul intrare/ieşire:dicsi.in, dicsi.outSursăFMI No Stress 2017
AutorEugenie Daniel PosdarascuAdăugată defmins7Fmi No Stress 7 fmins7
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.indicsi.out
5
3
3 2 1 1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?