Fișierul intrare/ieșire | ssce.in, ssce.out | Sursă | Lot Vaslui 2014 - Baraj 3 |
---|---|---|---|
Autor | Marius Nicoli | Adăugată de | Tinca Matei • TincaMatei |
Timp de execuție pe test | 1.25 sec | Limită de memorie | 16384 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
Ssce (Lot Juniori)
Avem la dispoziție un șir X cu n numere naturale date într-o bază b. Trebuie determinat un subșir al șirului dat care are următoarele proprietăți:
- Fiecare cifră a bazei b: 0, 1, …, b–1 apare, în total, în numerele acestui subșir de același număr de ori.
- În orice prefix al subșirului determinat, diferența dintre numerele de apariții ale oricăror 2 cifre cuprinse între 0 și b-1 este cel mult k (un prefix al subșirului determinat reprezintă o secvență de valori din subșir începând cu primul element al subșirului).
h2 Cerință
Determinați numărul maxim de elemente ale unui astfel de subșir.
Date de intrare
Pe prima linie a fișierului ssce.in se găsesc 3 numere naturale n, b, k, în această ordine, separate prin câte un spațiu, care au semnificația din enunț.
Pe linia a 2-a se găsesc, separate prin câte un spațiu, n numere naturale, elementele șirului X.
Date de ieșire
Pe prima linie a fișierului ssce.out se găsește un singur număr natural ce reprezintă valoarea cerută.
Restricții
- 1 ≤ n ≤ 10000
- 2 ≤ b ≤ 4
- 1 ≤ k ≤ 5
- 0 ≤ Xi ≤ 100000 (în baza b)
- Se garantează că în toate fișierele de test, elementele șirului X au cifrele cuprinse între 0 și b – 1 inclusiv.
Exemplu
ssce.in | ssce.out |
---|---|
5 2 1 1 10000 100 1111 0 |
2 |
Explicație
Soluția este dată de elementele 1 și 100. Ambele cifre ale bazei b apar de câte 2 ori în aceste numere. Dacă am fi considerat subșirul cu toate elementele șirului dat, numărul de apariții ale ambelor cifre ar fi fost egal însă nu s-ar fi îndeplinit a doua constrângere (de exemplu, prefixul de lungime 2 al acestuia, format din 1 și 10000 are diferența 2 între numărul de apariții ale cifrei 0 și numărul de apariții ale cifrei 1).