| Fişierul intrare/ieşire: | ssce.in, ssce.out | Sursă | Lot Vaslui 2014 - Baraj 3 Juniori |
| Autor | Marius Nicoli | Adăugată de |  Alexandru Valeanu •AlexandruValeanu |
| Timp execuţie pe test | 0.375 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | ssce.out | Explicaţ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
