problema/scoici

Scoici

== include(page="template/taskheader" task_id="scoici") ==

Cum se apropie vara, Denisa şi Alexandra, prietene bune din copilărie, merg la mare. Plimbându-se toată ziua pe malul mării încep să strângă scoici. După ce strâng N scoici, Alexandra le înşiră pe o sfoară si constată că sunt colorate în maxim C culori. Denisa doreşte acum să aleagă dintre cele N scoici, o secvenţă armonioasă, cât mai lungă, pentru a-şi face un colier frumos. Colier armonios înseamnă să aibă scoici de toate culorile disponibile şi fiecare să aibă aceeaşi frecvenţă de aparitie. Cum numărul de scoici strâns poate fi destul de mare (pentru că fetele au multa răbdare), vă este cerut ajutorul.

Cum se apropie vara, Denisa şi Alexandra, prietene bune din copilărie, merg la mare. Plimbându-se toată ziua pe malul mării încep să strângă scoici. După ce strâng $N$ scoici, Alexandra le înşiră pe o sfoară si constată că sunt colorate în maxim $C$ culori. Denisa doreşte acum să aleagă dintre cele $N$ scoici, o secvenţă armonioasă, cât mai lungă, pentru a-şi face un colier frumos. Colier armonios înseamnă să aibă scoici de toate culorile disponibile şi fiecare să aibă aceeaşi frecvenţă de aparitie. Cum numărul de scoici strâns poate fi destul de mare (pentru că fetele au multa răbdare), vă este cerut ajutorul.

h2. Cerinţă

Ajutaţi-o pe Denisa să determine cea mai lungă secvenţă armonioasă din cele N scoici pentru a-şi face cel mai frumos colier.

Ajutaţi-o pe Denisa să determine cea mai lungă secvenţă armonioasă din cele $N$ scoici pentru a-şi face cel mai frumos colier.

h2. Date de intrare

Fişierul de intrare $scoici.in$ contine pe prima linie numărul de scoici N şi numărul de culori C. A doua linie va conţine culorile scoicilor culese, codificate prin numere naturale de la 1 la C.

Fişierul de intrare $scoici.in$ contine pe prima linie numărul de scoici $N$ şi numărul de culori $C$. A doua linie va conţine culorile scoicilor culese, codificate prin numere naturale de la $1$ la $C$.

h2. Date de ieşire

h2. Restricţii

* 1 ≤ N ≤ 100 000
* 2 ≤ C ≤ 10

* $1 ≤ N ≤ 100.000$
* $2 ≤ C ≤ 10$

* Dacă sunt mai multe solutii optime ca lungime, determinaţi pe cea cu poziţia initială mai mică.
* Se garantează existenţa unei soluţii precum şi faptul că în sirul dat există cel putin o scoică din fiecare culoare.

h3. Explicaţie

Secventa cea mai lungă este 1 2 1 3 3 2, cu frecvenţele egale cu 2 şi toate cele 3 culori sunt prezente.

Secventa cea mai lungă este $1 2 1 3 3 2$, cu frecvenţele egale cu $2$ şi toate cele $3$ culori prezente.

== include(page="template/taskfooter" task_id="scoici") ==

public

task: scoici

4512