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

Просмотры: 69
Изменено: 12 октября 2024

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

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

Пример входного файла:
\(9\)
\(7\)
\(5\)
\(6\)
\(12\)
\(5\)
\(11\)
\(8\)
\(16\)
\(14\)

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

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

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

Решение:

C++


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

using namespace std;

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

    for(string fn: files) {
        fstream in(base + fn);
        int N;
        int n7 = 0, n2 = 0, n14 = 0, q = 0;
        in >> N;

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

        for(int i = 0; i < N - 7; i++) {
            if (v[i] % 14 == 0)
                n14++;
            else if (v[i] % 7 == 0)
                n7++;
            else if (v[i] % 2 == 0)
                n2++;
            q += n14;
            if (v[i + 7] % 14 == 0) 
                q += i + 1 - n14;
            else if (v[i + 7] % 7 == 0) 
                q += n2;
            else if (v[i + 7] % 2 == 0)
                q += n7;
        }

        cout << q << '\n';

    }
}

Ответ: \(30 \,\, 360137507\)