Fișierul intrare/ieșire ssce.in, ssce.out Sursă Lot Vaslui 2014 - Baraj 3
Autor Marius Nicoli Adăugată de avatar TincaMatei Tinca Matei TincaMatei
Timp de execuție pe test 1.25 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A

Ssce (Lot Juniori)

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.

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
5 2 1
1 10000 100 1111 0
2

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii