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

<syntaxhighlight lang="python" line>

1. 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

1. 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

1. 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")

1. Rulează funcția 'solve' doar dacă acest script este rulat direct.

if __name__ == "__main__":

   solve()

</syntaxhighlight>