3708 - selectare

Avem un șir V format din n cifre nenule precum și două numere naturale L și K. Putem efectua următoarea operație: alegem L elemente aflate unul lângă altul în șir apoi selectăm K dintre ele pe care le eliminăm. Cele L - K cifre se așează una lângă alta formând un număr a cărui valoare ne interesează (cifrele nu își pot schimba ordinea relativă, adică se așează în ordinea crescătoare a indicilor lor în șirul inițial).

Cerința

Trebuie să determinăm valoarea cu număr maxim de apariții pe care o obținem cu acest procedeu. Dacă sunt mai multe valori care apar de număr maxim de ori o vom alege pe cea mai mică. Două posibilități se consideră distincte dacă diferă prin indicele în șirul dat inițial al cel puțin uneia dintre cifrele de același rang în numerele asociate.

Date de intrare

Fișierul de intrare input.txt conține pe prima linie valorile n, L, K, în această ordine, separate prin câte un spațiu. Pe linia a doua se află cele n cifre, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie cea mai mică valoare care are număr maxim de apariții.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ L ≤ 6
• L ≤ n
• 0 ≤ K ≤ 2

Exemplul 1

innput.txt:

8 4 0

2 1 2 1 2 1 2 3

output.txt:

1212

Explicație:

Avem de selectat secvențe de câte 4 cifre și nu trebuie să eliminăm nimic. Se formează numerele: 2121, 1212, 2121 și 1212, 2123. Avem două valori ce se pot forma și care apar de câte două ori și o valoare ce

se poate forma o dată. Valoarea 1212 se poate forma de două ori și este cea mai mică dintre cele cu acest număr de apariții.

Exemplul 2

input.txt

5 4 2

1 1 1 1 1

output.txt:

11

Explicație:

Evident că valoarea obținută nu poate fi decât 11. Ea se poate obține de 9 ori, cu cifrele de pe pozițiile: (1,2)(2,3)(3,4)(4,5)(1,3), (2,4)(3,5)(1,4)(2,5).

Exemplul 3

input.txt:

9999999999999 4 0

2 1 2 1 2 1 2 3

Output:

Invalid input constraints.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verify_constraints(N, L, K):

   if not (1 <= N <= 1000 and 1 <= L <= 6 and L <= N and 0 <= K <= 2 and K <= L - 1):
       print("Invalid input constraints.")
       exit()

with open("input.txt", "r") as fin, open("output.txt", "w") as fout:

   N, L, K = map(int, fin.readline().split())
   verify_constraints(N, L, K)
   v = list(map(int, fin.readline().split()))

   f = [0] * 1000000

   for s in range(L - K, L + 1):
       for i in range(1, N - s + 2):
           j = i + s - 1
           e = s - (L - K)

           if e == 0:
               val = int(.join(map(str, v[i - 1:j])))
               f[val] += 1

           if e == 1:
               for i1 in range(i + 1, j):
                   val = int(.join(map(str, v[i - 1:i1] + v[i1 + 1:j])))
                   f[val] += 1

           if e == 2:
               for i1 in range(i + 1, j - 1):
                   for i2 in range(i1 + 1, j):
                       val = int(.join(map(str, v[i - 1:i1] + v[i1 + 1:i2] + v[i2 + 1:j])))
                       f[val] += 1

   p = 10 ** L
   sol = max(range(p), key=lambda x: f[x])
   fout.write(str(sol))

</syntaxhighlight>