Editing 3067 - optime

Maria iubește numerele prime. Ea scrie pe o foaie de hârtie, în ordine strict crescătoare, un șir format din numerele prime care au cel puțin două cifre. Apoi, din numerele care conțin mai mult de două cifre taie cifrele din stânga, astfel încât să rămână exact două cifre. Dacă după tăierea cifrelor numărul obținut nu este cuprins între <code>10</code> și <code>99</code>, numărul este eliminat din șir. De exemplu, numărul prim <code>101</code>, care are trei cifre, nu va fi scris, deoarece i se taie cifra din stânga, rezultând numărul <code>01</code>, adică <code>1</code>, care nu are exact două cifre, deci după tăiere va fi eliminat din șir.

Maria umple un tabel cu <code>2 * k</code> linii și <code>k</code> coloane, astfel încât, parcurgându-l pe linii, de sus în jos și fiecare linie de la stânga la dreapta, se obțin numerele din șir. Studiind numerele din tabel, constată că printre acestea se află și numere care nu sunt prime. De exemplu, pentru <code>k = 4</code>, tabelul arată ca în imagine.

= Cerința =
Cunoscând un număr natural <code>k</code> nenul și un număr natural <code>x</code>, ajutați-o pe Maria:

1. Să determine suma numerelor din tabel care nu sunt prime. Dacă nu există numere care nu sunt prime, suma are valoarea <code>0</code>.

2. Să aleagă <code>x</code> coloane consecutive din tabel, astfel încât acestea să conțină, în total, un număr maxim de numere prime. Dacă există mai multe posibilități, se va alege secvența de coloane consecutive care are o valoare cât mai mare a coloanei de început din secvență. Să se determine numărul primei coloane din secvența aleasă, precum și numărul total de numere prime din secvență.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie o cifră <code>c</code> care poate să fie doar <code>1</code> sau <code>2</code>. Dacă <code>c = 1</code>, pe linia a doua se găsește un număr natural nenul <code>k</code> cu semnificația din enunț. Dacă <code>c = 2</code>, pe linia a doua se află două numere naturale nenule, <code>k</code> și <code>x</code>, cu semnificația din enunț.

= Date de ieșire =
Dacă valoarea lui <code>c</code> este <code>1</code>, atunci se va rezolva numai punctul 1 din cerință. În acest caz, fișierul de ieșire <code>output.txt</code> va conţine pe prima linie un număr natural reprezentând valoarea sumei determinate.

Dacă valoarea lui <code>c</code> este <code>2</code>, se va rezolva numai punctul 2 din cerință. În acest caz, fișierul de ieșire <code>output.txt</code> va conține pe prima linie un număr natural reprezentând numărul de ordine al primei coloane conform cerinței, iar pe linia a doua numărul de numere prime, conform cerinței.

= Restricții și precizări =

* <code>1 ≤ x ≤ k ≤ 200</code>

= Exemplul 1 =
input.txt:

1

4

output.txt:

286

Explicație:

Pentru <code>k = 4</code>, în tabel se află următoarele numere neprime: <code>27</code>, <code>39</code>, <code>49</code>, <code>51</code>, <code>57</code>, <code>63</code>, suma lor fiind <code>286</code>.

== Exemplul 2 ==
input.txt:

2

4 3

output.txt:

2

19

Explicație:

Coloana <code>1</code> conține <code>7</code> numere prime, coloana <code>2</code> conține <code>6</code> numere prime, coloana <code>3</code> conține <code>6</code> numere prime, iar coloana <code>4</code> conține <code>7</code> numere prime. Putem alege fie coloanele <code>1</code>, <code>2</code>, <code>3</code>, fie coloanele <code>2</code>, <code>3</code>, <code>4</code>, ambele variante conținând câte <code>19</code> numere prime. Se alege a doua variantă, pentru că are valoarea mai mare a coloanei de început a secvenței.

== Exemplul 3 ==
intput.txt:

2

99999999999999 3

Output:

Input-ul nu convine conditiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from math import sqrt

def verificare(n):
    if not(1<=n<=200):
        print("Input-ul nu convine conditiilor")
        exit()

N = 2000000

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

task, k, x = 0, 0, 0
a = [[0]*201 for _ in range(401)]
v = [0]*201
sp = [0]*201
s = 0
e = [0] * (N + 1)
prime = []

def ciur():
    global prime
    temp = 0
    
    e[0] = e[1] = 1
    for i in range(2, N + 1):
        if not e[i]:
            for j in range(i * 2, N + 1, i):
                e[j] = 1

    for i in range(10, N + 1):
        if i < 100 and not e[i]:
            prime.append(i)
        elif i > 100 and not e[i]:
            temp = i % 100
            if temp >= 10:
                prime.append(temp)

def read():
    global task, k, x
    task=int(fin.readline())

    if task == 1:
        k = int(fin.readline())
        verificare(k)
    if task == 2:
        k, x = map(int, fin.readline().split())
        verificare(k)

def build():
    global s
    p = 0

    for i in range(1, 2 * k + 1):
        for j in range(1, k + 1):
            a[i][j] = prime[p]
            s += a[i][j] * (e[a[i][j]] == 1)

            if a[i][j] > 10 and not e[a[i][j]]:
                v[j] += 1

            p += 1

def solve():
    global s
    if task == 1:
        fout.write(str(s))
    else:
        nr_prime = 0
        maxi = -1
        first = 0

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

        for i in range(x, k + 1):
            nr_prime = sp[i] - sp[i - x]
            if nr_prime >= maxi:
                maxi = nr_prime
                first = i - x + 1
        fout.write(str(first)+"\n")
        fout.write(str(maxi))

if __name__ == "__main__":
    ciur()
    read()
    build()
    solve()

</syntaxhighlight>