Editing 3708 - selectare

Avem un șir <code>V</code> format din <code>n</code> cifre nenule precum și două numere naturale <code>L</code> și <code>K</code>. Putem efectua următoarea operație: alegem <code>L</code> elemente aflate unul lângă altul în șir apoi selectăm <code>K</code> dintre ele pe care le eliminăm. Cele <code>L - K</code> 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 <code>input.txt</code> conține pe prima linie valorile <code>n</code>, <code>L</code>, <code>K</code>, în această ordine, separate prin câte un spațiu. Pe linia a doua se află cele <code>n</code> cifre, separate prin câte un spațiu.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 1000</code>
* <code>1 ≤ L ≤ 6</code>
* <code>L ≤ n</code>
* <code>0 ≤ K ≤ 2</code>

== 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 <code>4</code> cifre și nu trebuie să eliminăm nimic. Se formează numerele: <code>2121</code>, <code>1212</code>, <code>2121</code> și <code>1212</code>, <code>2123</code>. 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 <code>1212</code> 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 <code>11</code>. Ea se poate obține de <code>9</code> ori, cu cifrele de pe pozițiile: <code>(1,2)(2,3)(3,4)(4,5)(1,3)</code>, <code>(2,4)(3,5)(1,4)(2,5)</code>.

== 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>