Fişierul intrare/ieşire:scoici.in, scoici.outSursă.campion 2005
AutorStefan GheorgheAdăugată deste_fanusGheorghe Stefan ste_fanus
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inscoici.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content