Fişierul intrare/ieşire:ssce.in, ssce.outSursăLot Vaslui 2014 - Baraj 3 Juniori
AutorMarius NicoliAdăugată deAlexandruValeanuAlexandru Valeanu AlexandruValeanu
Timp execuţie pe test0.75 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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, …, 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 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.inssce.outExplicaţie
5 2 1
1 10000 100 1111 0
2
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).
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?