Задача 6268. Источник: Поляков. Задание КИМ 27
(А. Кабанов) На вход программы поступает последовательность из N натуральных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязательно должны стоять в последовательности рядом, порядок в паре неважен). Необходимо определить количество пар, для которых сумма элементов кратна 17, а номера элементов в последовательности отличаются не более, чем на K.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит число N – количество чисел, во второй строке K – максимальную разницу между номерами элементов (1 ≤ N ≤ 10 000 000, N > K). В каждой из следующих N строк записаны элементы последовательности (все числа неотрицательные, не превышающие 2 000 000).
Пример входного файла:
10
4
62
13
99
40
74
62
73
63
84
53
В этой последовательности условию удовлетворяют 5 пар: (62, 40), (62, 74), (40, 62), (74, 62), (73, 63). Ответ: 5.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Сохраним в массиве а остатки от деления чисел на 17. Одновременно в массиве ka будем подсчитывать, сколько данный остаток встретился до данного элемента включительно. Для заполнения массива ka, будем подсчитывать текущее количество элементов с различными остатками в массиве count. В цикле по индексам первых элементов пар будем сохранять в массиве last последнее количество элементов с различными остатками и искать последний элемент диапазона, остаток которого дает сумму кратную 17. Количество элементов, образующих пары с первым элементов будет разностью между количеством элементов для значения последнего подходящего элемента диапазона и сохраненным значением в массиве last.
Python
f = open('27-150b.txt')
n = int(f.readline())
k = int(f.readline())
count = [0] * 17
a = []
ka = []
for i in f:
a.append(int(i) % 17)
count[a[-1]] += 1
ka.append(count[a[-1]])
res = 0;
last = [0] * 17
for i in range(n - 1):
last[a[i]] = ka[i]
for j in range(min(i + k, n - 1), i, -1):
if a[i] == 0 and a[j] == 0:
res += ka[j] - last[0]
break
elif a[i] != 0 and a[j] == 17 - a[i]:
res += ka[j] - last[a[j]]
break
print(res)
PascalABC
var
n, k, res, i, j: Integer;
a, ka: array [1..100000] of Integer;
count, last: array [0..16] of Integer;
f: TEXT;
begin
for i := 0 to 16 do
begin
count[i] := 0;
last[i] := 0;
end;
Assign(f, '27-150b.txt');
Reset(f);
Readln(f, n);
Readln(f, k);
for i := 1 to n do
begin
Readln(f, a[i]);
a[i] := a[i] mod 17;
count[a[i]] := count[a[i]] + 1;
ka[i] := count[a[i]];
end;
res := 0;
for i := 1 to n - 1 do
begin
last[a[i]] := ka[i];
for j := (i + k > n) ? n : i + k downto i + 1 do
if (a[i] = 0) and (a[j] = 0) then
begin
res := res + ka[j] - last[0];
break;
end
else if (a[i] <> 0) and (a[j] = 17 - a[i]) then
begin
res := res + ka[j] - last[a[j]];
break;
end;
end;
Writeln(res);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-150b.txt");
int n, k;
f >> n >> k;
int a[100000], ka[100000], count[17], last[17];
for (int i = 0; i < 17; i++)
{
count[i] = 0;
last[i] = 0;
}
for (int i = 0; i < n; i++)
{
f >> a[i];
a[i] %= 17;
count[a[i]]++;
ka[i] = count[a[i]];
}
int res = 0;
for (int i = 0; i < n - 1; i++)
{
last[a[i]] = ka[i];
for (int j = (i + k > n - 1) ? n - 1 : i + k; j > i; j--)
if (a[i] == 0 && a[j] == 0)
{
res += ka[j] - last[0];
break;
}
else if (a[i] != 0 and a[j] == 17 - a[i])
{
res += ka[j] - last[a[j]];
break;
}
}
cout << res << endl;
}
Ответ
15079 128655900