Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | scoici.in, scoici.out | Sursă | .campion 2005 |
| Autor | Stefan Gheorghe | Adăugată de |  Gheorghe Stefan •ste_fanus |
| 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
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.
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.
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.
Date de ieşire
În fişierul de ieşire scoici.out se vor afişa două numere, poziţia în sirul de scoici de unde incepe colierul şi lungimea acestuia.
Restricţii
- 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.
Exemplu
| scoici.in | scoici.out |
|---|---|
| 9 3 1 2 1 3 3 2 1 1 3 | 1 6 |
Explicaţie
Secventa cea mai lungă este 1 2 1 3 3 2, cu frecvenţele egale cu 2 şi toate cele 3 culori prezente.
