Fişierul intrare/ieşire: | maxk.in, maxk.out | Sursă | preOJI 2016, clasa a 10-a |
Autor | Gemene Narcis - Gabriel | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 12288 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Maxk
Concurenţă acerbă! Ojilă participă azi la olimpiada de informatică faza pe bancă. Contracandidat îi este Onilă, colegul şi rivalul lui. Ei au de rezolvat o problemă şi cine o rezolvă promovează la faza pe rândul de la geam. Se dă un şir de N numere naturale şi un număr natural K. Se cere să se elimine o secvenţă de lungime minimă astfel încât fiecare element din şirul rămas să apară de maximum K ori.
Date de intrare
Fişierul de intrare maxk.in conţine pe prima linie numerele N şi K. Pe următoarea linie se află N numere naturale separate prin câte un spaţiu reprezentând elementele şirului.
Date de ieşire
Fişierul de ieşire maxk.out va conţine un singur număr reprezentând lungimea minimă a secvenţei.
Restricţii
- 1 ≤ K,N ≤ 1 000 000
- Elementele şirului sunt numere naturale nenule mai mici sau egale cu 100 000.
Exemplu
maxk.in | maxk.out |
---|---|
6 1 3 3 3 2 1 2 | 3 |
Explicaţie
Secvenţa care se elimină este 3,3,2.