ssce

Time limit: 0.2s Memory limit: 32MB Input: ssce.in Output: ssce.out

Avem la dispoziţie un şir XX cu nn numere naturale date într-o bază bb. Trebuie determinat un subşir al şirului dat care are următoarele proprietăţi:

  • Fiecare cifră a bazei bb: 00, 11, \dots, b1b - 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 22 cifre cuprinse între 00 şi b1b - 1 este cel mult kk (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 33 numere naturale nn, bb, kk, î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, nn numere naturale, elementele șirului XX.

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

  • 1n10 0001 \leq n \leq 10 \ 000
  • 2b42 \leq b \leq 4
  • 1k51 \leq k \leq 5
  • 0Xi100 0000 \leq X_i \leq 100 \ 000 (în baza bb)
  • Se garantează că în toate fișierele de test, elementele șirului xx au cifrele cuprinse între 00 și b1b - 1, inclusiv.

Exemplu

ssce.in

5 2 1
1 10000 100 1111 0

ssce.out

2

Explicație

Soluţia este dată de elementele 11 şi 100100. Ambele cifre ale bazei bb apar de câte 22 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 22 al acestuia, format din 11 şi 1000010000 are diferenţa 22 între numărul de apariţii ale cifrei 00 şi numărul de apariţii ale cifrei 11).

Log in or sign up to be able to send submissions!