Задание 27. Информатика. ЕГЭ. Поляков-2677

Просмотры: 146
Изменено: 23 ноября 2024

(А. Жуков) Имеется набор данных, состоящий из положительных целых чисел. Необходимо определить количество пар элементов \((a_i, \, a_j)\) этого набора, в которых \(1 \leqslant i+5 \leqslant j \leqslant N\), сумма элементов нечётна, а произведение делится на \(13\).

Входные данные. Даны два входных файла (файл \(A\) и файл \(B\)), каждый из которых содержит в первой строке количество чисел \(N\) \((1 \leqslant N \leqslant 100000)\). Каждая из следующих \(N\) строк содержит одно натуральное число, не превышающее \(10~000\).

Пример входного файла:

\(7\)
\(4\)
\(14\)
\(27\)
\(39\)
\(7\)
\(2\)
\(13\)

Для указанных входных данных количество подходящих пар должно быть равно \(2\). В приведённом наборе имеются две пары \((4, \, 13)\) и \((14, \, 13)\), сумма элементов которых нечётна, произведение кратно \(13\) и индексы элементов последовательности отличаются не менее, чем на \(5\).

В ответе укажите два числа: сначала количество подходящих пар для файла \(А\), затем для файла \(B\).

Файл с данными

Решение:

C++


#include<iostream>
#include<fstream>
#include<string>
#include<vector>

using namespace std;

int32_t main() {
    string base = "";
    string fnames[] = {"27-A.txt", "27-B.txt"};

    for (string fn: fnames) {
        ifstream in(base + fn);
        int N;
        in >> N;
        vector<int> v(N);
        int p = 0;
        int evodd[2] = {0, 0}, evodd13[2] = {0, 0};

        for(int i = 0; i < N; i++)
            in >> v[i];

        for(int i = 0; i < N-5; i++) {
            if (v[i] % 13) 
                evodd[v[i] % 2]++;
            else 
                evodd13[v[i] % 2]++;
            p += evodd13[(v[i+5] % 2 + 1) % 2];
            if (v[i+5] % 13 == 0)
                p += evodd[(v[i+5] % 2 + 1) % 2];
        }

        cout << p << '\n';
    }
}

Ответ: \(6 \,\, 129920689\)