Задача 5314. Источник: Поляков. Задание КИМ 27
(Л. Шастин) На вход программе поступает последовательность натуральных чисел. Рассматриваются всевозможные пары различных ненулевых элементов последовательности, количество нулей между которыми кратно 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