Editing 2411 - secvp

Se consideră un şir cu <code>N</code> numere naturale <code>a[1]</code>, <code>a[2]</code>, …, <code>a[N]</code>. Asupra unui element <code>a[i]</code> din şir se pot efectua operaţii de incrementare (adunare cu <code>1</code>: <code>a[i] = a[i] + 1</code>) sau decrementare (scădere cu <code>1</code>: <code>a[i] = a[i] - 1</code>). Fiecare element din şir poate fi incrementat sau decrementat de oricâte ori.

= Cerința =
Dat fiind șirul celor <code>N</code> numere naturale, să se determine:

a. numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime;

b. numărul minim de operații (incrementări şi decrementări) ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvență de lungime <code>K</code> formată numai din numere prime.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>N</code> şi <code>K</code>, iar pe următoarea linie <code>N</code> numere naturale. Numerele scrise pe aceeași linie sunt separate prin spații.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> conţine pe prima linie un număr natural <code>T</code>, reprezentând numărul total minim de operaţii necesare pentru a transforma toate numerele din şir în numere prime. Pe a doua linie vor fi scrise două numere naturale separate prin spaţiu <code>minK nrsK</code>, unde <code>minK</code> reprezintă numărul minim de operaţii ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvenţă de lungime <code>K</code> formată numai din numere prime, iar <code>nrsK</code> reprezintă numărul de secvenţe de lungime <code>K</code> care se pot obţine cu acelaşi număr <code>minK</code> de operaţii de incrementare/decrementare.

= Restricții și precizări =

* <code>2 ≤ K ≤ N ≤ 100.000</code>

= Exemplul 1 =
input.txt:

7 3

15 3 8 26 22 10 14

output.txt:

9

3 2

Explicație:

Pentru a transforma <code>15</code> în număr prim sunt necesare <code>2</code> incrementări.

Pentru a transforma <code>3</code> în număr prim sunt necesare <code>0</code> operaţii.

Pentru a transforma <code>8</code> în număr prim e necesară <code>1</code> decrementare.

Pentru a transforma <code>26</code> în număr prim sunt necesare <code>3</code> decrementări.

Pentru a transforma <code>22</code> în număr prim e necesară <code>1</code> incrementare.

Pentru a transforma <code>10</code> în număr prim e necesară <code>1</code> incrementare.

Pentru a transforma <code>14</code> în număr prim e necesară <code>1</code> decrementare.

Numărul total de operaţii necesare este <code>9</code>.

Numărul minim de operaţii necesare pentru a obţine o secvenţă de lungime <code>K</code> este <code>3</code>. Cele două secvenţe de lungime <code>K</code> ce necesită <code>3</code> operaţii sunt <code>a[1], a[2], a[3]</code> şi <code>a[5], a[6], a[7]</code>.

== Exemplul 2 ==
input.txt

9999999999 3

15 3 8 26 22 10 14

Output:

Invalid input. Please ensure 2 <= K <= N <= 100,000.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import bisect

def validate_input(n, k):
    if not (2 <= k <= n <= 100000):
        print("Invalid input. Please ensure 2 <= K <= N <= 100,000.")
        exit()

fin = open("input.txt", "r")
fout = open("output.txt", "w")

N = 1000100

e = [0] * (N + 1)
v = []
a = [0] * 100001
iteratii = [0] * 100001
sp = [0] * 100001

def ciur():
    global v
    e[0] = e[1] = 1

    for i in range(2, N + 1):
        if not e[i]:
            v.append(i)

            for j in range(i * 2, N + 1, i):
                e[j] = 1

def read_solve1():
    global n, k, a, iteratii, sp

    n, k = map(int, fin.readline().split())
    validate_input(n, k)
    s = 0

    l=list(map(int, fin.readline().split()))

    for i in range(1, n + 1):
        x = l[i-1]

        it = bisect.bisect_left(v, x)
        it2 = bisect.bisect_right(v, x)

        d1 = it
        d2 = it2

        if e[x]:
            if d1 > 0:
                s += min(abs(x - v[d1 - 1]), abs(x - v[d2]))
                iteratii[i] = min(abs(x - v[d1 - 1]), abs(x - v[d2]))

                if iteratii[i] == abs(x - v[d1 - 1]):
                    iteratii[i] *= -1
            else:
                s += abs(x - v[d2])
                iteratii[i] = abs(x - v[d2])

        a[i] = x + iteratii[i]

        if iteratii[i] < 0:
            iteratii[i] *= -1

        sp[i] = sp[i - 1] + iteratii[i]

    fout.write(str(s)+"\n")

def solve2():
    global n, k, sp, mini, secv

    temp = 0
    mini = float('inf')
    secv = 0

    for i in range(k, n + 1):
        temp = sp[i] - sp[i - k]

        if temp < mini:
            mini = temp
            secv = 1
        elif temp == mini:
            secv += 1

    fout.write(str(mini)+" ")
    fout.write(str(secv))

if __name__ == "__main__":
    ciur()
    read_solve1()
    solve2()

</syntaxhighlight>