Ssce

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

* 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ţă

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

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

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.

* $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 |_. Explicaţie |

table(example). |_. ssce.in |_. ssce.out |

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

| 1 10000 100 1111 0
|
 
h3. 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).

== include(page="template/taskfooter" task_id="ssce") ==