Editing 2411 - secvp (section)

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