2411 - secvp

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

Cerința

Dat fiind șirul celor N 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 K formată numai din numere prime.

Date de intrare

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

Date de ieșire

Fișierul de ieșire output.txt conţine pe prima linie un număr natural T, 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 minK nrsK, unde minK reprezintă numărul minim de operaţii ce trebuie să fie efectuate asupra elementelor şirului astfel încât să existe o secvenţă de lungime K formată numai din numere prime, iar nrsK reprezintă numărul de secvenţe de lungime K care se pot obţine cu acelaşi număr minK de operaţii de incrementare/decrementare.

Restricții și precizări

• 2 ≤ K ≤ N ≤ 100.000

Exemplul 1

input.txt:

7 3

15 3 8 26 22 10 14

output.txt:

9

3 2

Explicație:

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

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

Pentru a transforma 8 în număr prim e necesară 1 decrementare.

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

Pentru a transforma 22 în număr prim e necesară 1 incrementare.

Pentru a transforma 10 în număr prim e necesară 1 incrementare.

Pentru a transforma 14 în număr prim e necesară 1 decrementare.

Numărul total de operaţii necesare este 9.

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

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>