Задача 6801. Источник: Поляков. Задание КИМ 27
(Е. Джобс) В файле записана последовательность показаний прибора. Характеристическое число последовательности – это количество последовательностей показаний, длины которых не меньше К и сумма элементов которых делится на 111 без остатка. Определите, характеристическое число для предложенных последовательностей.
Входные данные. Даны два входных файла (файл A и файл B), каждый из которых в первой строке содержит натуральное число N (2 < N ≤ 5 000 000) – количество показаний, и натуральное число К (1 < K < N) – минимально допустимую длину подходящих последовательностей. Каждая из следующих N строк содержит одно натуральное число, не превышающее 1000 – показание прибора.
Пример входного файла:
6 3
4
6
2
6
3
1
Пусть требуется найти последовательности, сумма которых делится на 10. При таких исходных данных подходит только одна последовательность: (6, 3, 1). Последовательность (4, 6) не подходит, так как в ней всего 2 элемента, а требуется по меньшей мере K = 3. Ответ: 1.
В ответе укажите два числа: сначала искомое значение для файла А, затем для файла B.
Решение
Эффективное решение основано на использовании префиксных сумм, но прямой перебор пар сумм на втором файле будет работать долго. На C++ такое решение требует нескольких десятков секунд, на PascalABC - больше минуты, а на Python - пару часов.
Python
f = open("27-171a.txt")
n, k = map(int, f.readline().split())
p = [0]
for i in f:
p.append(p[-1] + int(i))
r = 0
for i in range(n - k + 1):
for j in range(i + k, n + 1):
if (p[j] - p[i]) % 111 == 0:
r += 1
print(r)
PascalABC
var
n, k, r, x, i, j: Integer;
p: array [1..207398] of Integer;
f: TEXT;
begin
Assign(f, '27-171b.txt');
Reset(f);
Readln(f, n, k);
p[1] := 0;
for i := 2 to n + 1 do
begin
Readln(f, x);
p[i] := p[i - 1] + x;
end;
r := 0;
for i := 1 to n - k + 1 do
for j := i + k to n + 1 do
if (p[j] - p[i]) mod 111 = 0 then
r := r + 1;
Writeln(r);
end.
C++
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream f;
f.open("27-171b.txt");
int n, k;
f >> n >> k;
int* p = new int[207398];
p[0] = 0;
for (int i = 1; i <= n + 1; i++)
{
int x;
f >> x;
p[i] = p[i - 1] + x;
}
int r = 0;
for (int i = 0; i <= n - k; i++)
for (int j = i + k; j <= n; j++)
if ((p[j] - p[i]) % 111 == 0)
r++;
cout << r << endl;
delete[] p;
}
Для более эффективного решения будем сохранять позиции префиксных сумм с различными остатками от деления на 111. После обработки всех данных перебираем пары позиций для каждого остатка от деления на 111. Если разница позиций не менее k, то учитываем такую пару. Для каждой позиции вычитаемой префиксной суммы достаточно найти первую уменьшаемую префиксную сумму с расстоянием не менее k. Все позиции после нее будут иметь еще большую дистанцию. Это еще больше ускорит решение. Но даже такое решение на Python обрабатывает второй файл около половины минуты.
Python
f = open("27-171b.txt")
n, k = map(int, f.readline().split())
p = [[] for i in range(111)]
p[0].append(0)
s = 0
for i in range(1, n + 1):
s += int(f.readline());
p[s % 111].append(i)
r = 0
for z in p:
for i in range(len(z) - 1):
for j in range(i + 1, len(z)):
if z[j] - z[i] >= k:
r += len(z) - j
break
print(r)
PascalABC
var
n, k, r, x, s, z, i, j: Integer;
p: array [0..110] of array of Integer;
f: TEXT;
begin
Assign(f, '27-171b.txt');
Reset(f);
Readln(f, n, k);
for i := 0 to 110 do
p[i] := new Integer[0];
p[0] := p[0] + Arr(0);
s := 0;
for i := 1 to n do
begin
Readln(f, x);
s := s + x;
p[s mod 111] := p[s mod 111] + Arr(i);
end;
r := 0;
for z := 0 to 110 do
for i := 0 to p[z].Length - 2 do
for j := i + 1 to p[z].Length - 1 do
if p[z][j] - p[z][i] >= k then
begin
r := r + p[z].Length - j;
break;
end;
Writeln(r);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f;
f.open("27-171b.txt");
int n, k;
f >> n >> k;
vector<int> p[111];
p[0].push_back(0);
int s = 0;
for (int i = 1; i <= n; i++)
{
int x;
f >> x;
s += x;
p[s % 111].push_back(i);
}
int r = 0;
for (int z = 0; z < 111; z++)
for (int i = 0; i < p[z].size() - 1; i++)
for (int j = i + 1; j < p[z].size(); j++)
if (p[z][j] - p[z][i] >= k)
{
r += p[z].size() - j;
break;
}
cout << r << endl;
}
Ответ
4398 108618221