Se consideră numerele naturale n, k şi p şi un şir de n numere din mulţimea {1, 2, 3}. Acest şir îl împărţim în mai multe secvenţe de lungime cel mult k astfel încât, dacă în fiecare secvenţă notăm cu a1 numărul de valori de 1, cu a2 numărul de valori de 2 şi cu a3 numărul de valori 3, atunci să fie îndeplinite condiţiile (unde prin |x| am notat modulul lui x):
|a1 – a2| <= p cu condiţia ca a1şi a2 să fie strict pozitive (dacă a1 şi/sau a2 sunt 0, condiţia nu trebuie verificată)
|a2 – a3| <= p cu condiţia ca a2 şi a3 să fie strict pozitive (dacă a2 şi/sau a3 sunt 0, condiţia nu trebuie verificată)
|a1 – a3| <= p cu condiţia ca a1 şi a3 să fie strict pozitive (dacă a1 şi/sau a3 sunt 0, condiţia nu trebuie verificată)
De exemplu, pentru n=13, k=8, p=1, şirul 1,2,1,1,2,3,3,2,2,2,1,1,3 il putem împărţi în două secvenţe: 1,2,1,1,2 şi 3,3,2,2,2,1,1,3. În prima secvenţă a1=3, a2=2, a3=0 şi |a1 – a2| <= 1, iar celelalte două module nu se vor calcula, pentru că a3 este 0. În secvenţa a doua, a1=2, a2=3, a3=3 şi deci diferenţa în modul dintre oricare două este mai mică sau egală cu 1.
Împărţirea în secvenţe nu este unică. Şirul din exemplul de mai sus se poate împărţi şi în 3 secvenţe de lungime cel mult k. Prima: 1,2,1,1,2,3,3, a doua: 2,2,2,1,1 şi a treia: 3
Cerinţă
Scrieţi un program care împarte şirul într-un număr minim de secvenţe de lungime cel mult k astfel încât fiecare secvenţă să respecte condiţiile.
Date de intrare
Fişierul de intrare 123.in conţine pe prima linie numerele n k p separate printr-un spaţiu. Pe linia a doua se află şirul de n valori din mulţimea {1, 2, 3}, valori scrise fără spaţiu între ele.
Date de ieşire
Fişierul de ieşire 123.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numărul minim de secvenţe în care se poate împărţi şirul.