== include(page="template/taskheader" task_id="ssce") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $ssce.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $ssce.out$ ...
Pe prima linie a fişierului $ssce.out$ se găseşte un singur număr natural ce reprezintă valoarea cerută.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n ≤ 10000$
* $2 ≤ b ≤ 4$
* $1 ≤ k ≤ 5$
* $0 ≤ X[~i~] ≤ 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.
h2. Exemplu
table(example). |_. ssce.in |_. ssce.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. 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$).
|
== include(page="template/taskfooter" task_id="ssce") ==
