Miawinator: Pagină nouă: 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 n...

2024-01-05T01:50:43Z

Pagină nouă: 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 n...

New page

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>

2411 - secvp - Revision history