Simulation - Lot 2014 Baraj 3 Juniori | ssce

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$, $\dots$, $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).

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 doua 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 și precizări

• $1 \leq n \leq 10 \ 000$
• $2 \leq b \leq 4$
• $1 \leq k \leq 5$
• $0 \leq X_i \leq 100 \ 000$ (î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

5 2 1
1 10000 100 1111 0

ssce.out

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$).