Программное решение задач ЕГЭ по информатике

Задача 5314. Источник: Поляков. Задание КИМ 27

Страница задачи 5314

(Л. Шастин) На вход программе поступает последовательность натуральных чисел. Рассматриваются всевозможные пары различных ненулевых элементов последовательности, количество нулей между которыми кратно K либо равно нулю. Необходимо найти количество таких пар с суммой элементов, кратной D.

Входные данные. Даны два входных файла (файл A и файл B), содержит в первой строке число N (2 ≤ N ≤ 5 000 000) – количество чисел в последовательности, а также числа K и D. Каждая из следующих N строк содержит одно натуральное число, не превышающее 10000.

Пример входного файла:
8 2 2
5
0
3
0
0
0
1
9

В этой последовательности можно выбрать три подходящих пары: (5; 1), (5; 9), (1; 9). Между числами в каждой паре чётное количество нулей, а сумма элементов каждой из них тоже чётна. Ответ: 3.

В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.

Решение

Наиболее простым и относительно эффективным решением для компилируемых языков будет создание массива k0, где будет подсчитываться количество нулей до данного элемента. Таким образом, количество нулей между элементами можно получить через разность значений данного массива. На Pascal и C++ второй файл обрабатывается не более нескольких минут, но на Python такое решение работает слишком долго.

PascalABC

var
    n, k, d, count, i, j: Integer;
    a: array [1..200000] of Integer;
    k0: array [0..200000] of Integer;
    f: TEXT;
begin
    Assign(f, '27-118b.txt');
    Reset(f);
    Readln(f, n, k, d);
    k0[0] := 0;
    for i := 1 to n do
    begin
        readln(f, a[i]);
        if a[i] = 0 then
            k0[i] := k0[i - 1] + 1
        else
            k0[i] := k0[i - 1];
    end;
    count := 0;
    for i := 1 to n - 1 do
        if a[i] <> 0 then
            for j := i + 1 to n do
                if (a[j] <> 0) and ((a[i] + a[j]) mod d = 0) and
                   ((k0[j] - k0[i]) mod k = 0) then
                        count := count + 1;
    writeln(count);
end.

C++

Обратите внимание, что из-за большого размера массивов, память под них выделяется динамически. При создании статических массивов может возникать ошибка переполнения стека.

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("27-118b.txt");
    int n, k, d;
    f >> n >> k >> d;
    int* a = new int[200000];
    int* k0 = new int[200000];
    for (int i = 0; i < n; i++)
    {
        f >> a[i];
        if (a[i] == 0)
            if (i != 0)
                k0[i] = k0[i - 1] + 1;
            else
                k0[i] = 1;
        else
            if (i != 0)
                k0[i] = k0[i - 1];
            else
                k0[i] = 0;
    }
    int count = 0;
    for (int i = 0; i < n - 1; i++)
        if (a[i] != 0)
            for (int j = i + 1; j < n; j++)
                if (a[j] != 0 && (a[i] + a[j]) % d == 0 && (k0[j] - k0[i]) % k == 0)
                    count ++;
    cout << count;
    delete[] a;
    delete[] k0;
}

Более эффективным решением является создание двумерного массива p0, где будут хранится начальный и конечный индексы для каждого количества нулей. Этот массив позволит обрабатывать только те диапазоны пар, которые имеют нужную кратность количества нулей. Данное решение на компилируемых языках работает мгновенья и даже на Python находит ответ не более чем за несколько минут. В переменной max (mx) хранится максимальное количество нулей, а в k0 - количество нулей для i-го элемента.

Python

f = open('27-118b.txt')
n, k, d = map(int, f.readline().split())
a = [int(x) for x in f]
p0 = [[-1] * 2 for x in range(1000)]
mx = 0
for i in range(n):
    if a[i] == 0:
        mx += 1
        p0[mx][0] = i
    p0[mx][1] = i
count = 0
k0 = 0
for i in range(n - 1):
    if a[i] != 0:
        for h in range(k0, mx + 1, k):
            for j in range(max(i, p0[h][0]) + 1, p0[h][1] + 1):
                if (a[i] + a[j]) % d == 0:
                    count += 1
    else:
        k0 += 1
print(count)

PascalABC

var
    n, k, d, k0, max, count, i, h, j: Integer;
    a: array [1..200000] of Integer;
    p0: array [0..1000, 1..2] of Integer;
    f: TEXT;
begin
    Assign(f, '27-118b.txt');
    Reset(f);
    Readln(f, n, k, d);
    p0[0, 1] := 0;
    max := 0;
    for i := 1 to n do
    begin
        readln(f, a[i]);
        if a[i] = 0 then
        begin
            max := max + 1;
            p0[max, 1] := i;
        end;
        p0[max, 2] := i;
    end;
    count := 0;
    k0 := 0;
    for i := 1 to n - 1 do
        if a[i] <> 0 then
        begin
            h := k0;
            while h <= max do
            begin
                for j := ((i > p0[h, 1]) ? i : p0[h, 1]) + 1 to p0[h, 2] do
                    if (a[i] + a[j]) mod d = 0 then
                        count := count + 1;
                h := h + k;
            end;
        end
        else
            k0 := k0 + 1;
    writeln(count);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("27-118b.txt");
    int n, k, d;
    f >> n >> k >> d;
    int a[200000];
    int p0[1000][2];
    int max = 0;
    p0[0][0] = -1;
    for (int i = 0; i < n; i++)
    {
        f >> a[i];
        if (a[i] == 0)
        {
            max++;
            p0[max][0] = i;
        }
        p0[max][1] = i;
    }
    int count = 0, k0 = 0;
    for (int i = 0; i < n - 1; i++)
        if (a[i] != 0)
        {
            for (int h = k0; h <= max; h += k)
                for (int j = ((i > p0[h][0]) ? i : p0[h][0]) + 1; j <= p0[h][1]; j++)
                    if ((a[i] + a[j]) % d == 0)
                        count++;
        }
        else
            k0++;
    cout << count;
}

Ответ

8055 1097332

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: