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

#include <bits/stdc++.h>
using namespace std;
ifstream cin("numarspecial.in");
ofstream cout("numarspecial.out");
int n , a[1000001] , c1 , c2 , c3 , k , x , y;
int E[1000001];
int main()
{
    int max=1000000;
    for(int i = 2 ; i <= max ; i++) E[i] = 1;
    for(int i = 2 ; i*i <= max ; i++)
        if(E[i] == 1)
            for(int j = i*i; j <= max; j += i) E[j]=0;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
        if(a[i] % 9 == 0) c1++;
        if(i > 2)
            if(a[i-1] % 9 == 0 && E[a[i]] && E[a[i-2]]) c2++;
    }
    cout << c1 << '\n' << c2 << '\n';
    for(int i = 1 ; i <= n ; i++)
    {
        x = i - 1 ;
        y = i + 1 ;
        k = 0 ;
        if(i > 1 && i < n && a[i] % 9 == 0)
        while(E[a[x]] && E[a[y]])
        {
            k++;
            x--;
            y++;
            if(x < 1 && y > n) break;
        }
        if(k > c3) c3 = k;
    }
    cout << c3;
    return 0;

}