Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, сколько различных чисел встречается в записях Снегурочки. Дед Мороз и Снегурочка — волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.
Желательно, чтобы программа была эффективной как по времени работы, так и по используемой памяти. Программу будем считать эффективной по памяти, если используемая память не зависит от размера входных данных (то есть числа утренников). Программу будем считать эффективной по времени, если при увеличении размера входных данных N в t раз (t — любое число) время её работы увеличивается не более чем в t раз.
Описание входных данных
В первой строке вводится одно целое положительное число — количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D — количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений:
1 ≤ N ≤ 10000
1 ≤ D ≤ 100 (для каждого D)
D ≤ K ≤ 1000 (для каждой пары D, K)
Описание выходных данных
Программа должна вывести одно число — количество различных чисел в записях Снегурочки. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.
Пример входных данных:
7
10 58
15 315
20 408
100 1000
32 63
32 63
11 121
Пример выходных данных для приведённого выше примера входных данных:
2
Поскольку количество детей не превышает 100, остаться может не больше 99 конфет. Можно создать массив из 99 элементов и использовать их в качестве счётчиков, хранящих информацию о количестве записей каждого числа. Программа читает исходные данные, не запоминая их в массиве. Для каждой пары (D, K) количество оставшихся конфет определяется как остаток от деления K на D. Если этот остаток положителен, надо увеличить соответствующий счётчик. По окончании ввода и обработки данных надо подсчитать количество ненулевых элементов в массиве счётчиков.
Пример правильной и эффективной программы на языке Паскаль
program c4;
const DMAX=100; {максимально возможное количество
детей}
var
N: integer; {количество утренников}
D: integer; {количество детей на утреннике}
K: integer; {количество конфет}
r: integer; {остаток}
c: array[1..DMAX-1] of integer; {счетчики остатков}
i: integer;
m: integer; {счетчик разных чисел в записях}
begin
{предварительная очистка счетчиков}
for i:=1 to DMAX-1 do c[i]:=0;
readln(N);
{ввод данных, подсчет количества каждого остатка}
for i:=1 to N do begin
readln(D, K);
r := K mod D;
if r>0 then c[r]:=c[r]+1;
end;
{подсчет количества разных записей}
m:=0;
for i:=1 to DMAX-1 do begin
if c[i]>0 then m:=m+1;
end;
writeln(m);
end.
Возможны другие варианты решения. Например, можно вместо массива целочисленных счетчиков использовать массив данных логического типа, отмечающих только факт использования того или иного значения. Можно подсчитывать итоговое значение непосредственно в процессе ввода данных, увеличивая величину m на 1 каждый раз, когда встречается новое (не встречавшееся ранее) значение остатка.
Приводим эффективное решение Игоря Кудашева на Python 3.
n = int(input())
a = [0] * 100
count = 0
for i in range(n):
x, y = map(int,input().split())
a[y % x] += 1
for i in range(1, 100):
if a[i] != 0: count += 1
print(count)