1926 - NumarSpecial

Cerinţa

Se dă un şir format din n numere naturale . Un număr din şir se numeşte special de ordin k dacă suma cifrelor sale este divizibilă cu 9, iar cele k numere situate înaintea sa în şir şi cele k numere situate după el în şir sunt prime. Se cere să se afle câte numere speciale de ordin 0 şi câte numere speciale de ordin 1 sunt în şir, precum şi ordinul maxim al unui număr special din şir.

Date de intrare

Fișierul de intrare numarspecial.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieşire

Fișierul de ieșire numarspecial.out va conține pe prima linie numărul A, reprezentând numărul numerelor speciale de ordin 0 din şir, pe a doua linie numărul B, reprezentând numărul numerelor speciale de ordin 1 din şir, iar pe a treia linie ordinul maxim al unui număr special din şir.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• numerele din şir sunt mai mici decât 1.000.000
• dacă un număr este special de ordin k, atunci el este şi special de ordin k-1, k-2,…, 1 , 0
• prima cerinţă se notează cu 40p, a doua cu 40p şi a treia cu 20p
• pentru a obţine punctaje parţiale trebuie ca în fişierul numarspecial.out să afişaţi trei numere

Exemplu

numarspecial.in

13

3 72 5 7 2 2 891 2 13 29 5 27 1

numarspecial.out

3

2

4

Explicație

În şir sunt 3 numere speciale de ordin 0, şi anume 72, 891 şi 27 , două numere speciale de ordin 1, respectiv 72 şi 891, iar ordinul maxim al unui număr special este 4, al numărului 891 ( are 4 numere prime înaintea sa şi 4 după el).

Rezolvare

# Funcția 'is_prime' verifică dacă un număr este prim sau nu.
def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# Funcția 'is_special' verifică dacă un număr este special sau nu.
def is_special(n):
    return sum(int(digit) for digit in str(n)) % 9 == 0

# Funcția 'solve' rezolvă problema.
def solve():
    # Deschide și citește fișierul de intrare.
    with open('numarspecial.in', 'r') as fin:
        n = int(fin.readline().strip())
        numbers = list(map(int, fin.readline().split()))

    # Creează două liste: una pentru a verifica dacă fiecare număr este prim și alta pentru a verifica dacă fiecare număr este special.
    primes = [is_prime(x) for x in numbers]
    specials = [is_special(x) for x in numbers]

    # Calculează numărul de numere speciale de ordinul 0 și de ordinul 1.
    A = specials.count(True)
    B = sum(primes[i-1] and primes[i+1] and specials[i] for i in range(1, n-1))
    
    # Calculează ordinul maxim al unui număr special din șir.
    max_order = 0
    for k in range(2, n//2+1):
        for i in range(k, n-k):
            if sum(primes[j] for j in range(i-k, i+k+1)) == 2*k and specials[i]:
                max_order = k

    # Scrie rezultatele în fișierul de ieșire.
    with open('numarspecial.out', 'w') as fout:
        fout.write(f"{A}\n{B}\n{max_order}\n")

# Rulează funcția 'solve' doar dacă acest script este rulat direct.
if __name__ == "__main__":
    solve()