Avem la dispoziţie un şir cu numere naturale date într-o bază . Trebuie determinat un subşir al şirului dat care are următoarele proprietăţi:
- Fiecare cifră a bazei : , , , , 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 cifre cuprinse între şi este cel mult (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 numere naturale , , , î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, numere naturale, elementele șirului .
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
- (în baza )
- Se garantează că în toate fișierele de test, elementele șirului au cifrele cuprinse între și , inclusiv.
Exemplu
ssce.in
5 2 1
1 10000 100 1111 0
ssce.out
2
Explicație
Soluţia este dată de elementele şi . Ambele cifre ale bazei apar de câte 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 al acestuia, format din şi are diferenţa între numărul de apariţii ale cifrei şi numărul de apariţii ale cifrei ).