Областная олимпиада по информатике 2013-2014

Вам дана таблица $N × M$ , в каждой ячейке которой написана какая-то цифра. Будем считать, что число есть в этой таблице, если его можно “прочитать” в каком-то месте этой таблицы по горизонтали, по вертикали или по диагонали (вправо, вниз, или вправо-вниз).
Найдите количество и сумму всех простых чисел, состоящих не более чем из 6 цифр, которые есть в этой таблице. Если какое-то число повторяется несколько раз в разных местах таблицы, то все эти вхождения нужно учитывать. Числа не должны начинаться с нуля.

Входные данные

Первая строка входного файла содержит два целых числа $N$ и $M$ ($1 ≤ N, M ≤ 1500$). Следующие $N$ строк содержат по $M$ цифр, разделенных пробелом.

Выходные данные

Выведите два целых числа: количество и сумму всех найденных простых чисел.

Примеры:

Вход:

4 5 
1 2 3 4 5 
6 7 8 9 0 
0 9 8 7 6 
5 4 3 2 1

Ответ:

19 1547

Примечание:

Найденные простые числа (некоторые встречаются несколько раз): 2, 2, 3, 3, 5, 5, 7, 7, 17, 23, 43, 61, 67, 79, 83, 89, 97, 883. В 50% тестов $N, M ≤ 100$.

Комментарий/решение

Незнаю, правильно ли. Если есть ошибки, пожалуйста сообщите.

Использовал решето Эратосфена.

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mxll LLONG_MAX
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
const int INF = 1e9;
const int mod = 1e9+7;

vector <bool> sieve(1e6+1, true);

void configure() {
    sieve[0] = false; sieve[1] = false;
    for(int i=2; i<=1e3; i++) {
        if(sieve[i]) {
            for(int j=i*i; j<=1e6; j+=i) {
                sieve[j] = false;
            }
        }
    }
}

int main() {
    IOS;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    configure();

    int n, m;
    cin >> n >> m;
    vector <vector <int>> a(n+1, vector <int> (m+1));
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin >> a[i][j];
        }
    }
    ll s=0;
    set <int> st, os;

    // проходимся по горизонтали
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            int cur=0;
            for(int t=j; t<=min(m, j+5); t++) {
                cur = cur*10 + a[i][t];
                if(t==j && cur==0) break;
                if(sieve[cur]) {
                    st.insert(cur);
                    s += cur;
                }
            }
        }
    }
    // проходимся по вертикали
    for(int j=1; j<=m; j++) {
        for(int i=1; i<=n; i++) {
            int cur=0;
            for(int t=i; t<=min(n, i+5); t++) {
                cur = cur*10 + a[t][j];
                if(t==i && cur==0) break;
                if(sieve[cur]) {
                    int sz = st.size();
                    st.insert(cur);
                    if(st.size()!=sz) {
                        s += cur;
                    } else {
                        os.insert(cur);
                    }
                }
            }
        }
    }
    // проходимся диагонально
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            int cur=0;
            for(int t=0; t<=min(5, min(n-i, m-j)); t++) {
                cur = cur*10 + a[i+t][j+t];
                if(t==0 && cur==0) break;
                if(sieve[cur]) {
                    int sz = st.size();
                    st.insert(cur);
                    if(st.size()!=sz) {
                        s += cur;
                    } else {
                        os.insert(cur);
                    }
                }
            }
        }
    }
    // выводим ответ

    cout << st.size()+os.size() << " " << s;
}

C++

Copy