77_old. Дан набор из N натуральных чисел. Необходимо определить количество пар элементов (ai, aj) этого набора, в которых 1 ≤ i < j ≤ N и сумма элементов кратна 12. Напишите эффективную по времени и по памяти программу для решения этой задачи.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). �В каждой из последующих N строк записано одно натуральное число, �не превышающее 1000.
Пример входных данных:
5
7
5
6
12
24
Пример выходных данных для приведённого выше примера входных данных:
2
В приведённом наборе из 5 чисел имеются две пары (7, 5) и (12, 24), сумма элементов которых кратна 12.
var N, i, j : integer;
count: longint;
a: array[1..10000] of integer;
begin
readln(N);
for i:=1 to N do
readln(a[i]);
count:= 0;
for i:=1 to N-1 do
for j:=i+1 to N do
if (a[i]+a[j]) mod 12 = 0 then
count := count + 1;
writeln(count)
end.
var rem: array[0..11] of integer;
N, i, x: integer;
count: longint;
begin
for i:=0 to 11 do rem[i]:= 0;
readln(N);
for i:= 1 to N do begin
readln(x);
inc(rem[x mod 12])
end;
count:= (rem[0]*(rem[0]-1) +
rem[6]*(rem[6]-1)) div 2;
for i:= 1 to 5 do
count:= count + rem[i]*rem[12-i];
writeln(count)
end.
Идея решения основана на том, что если сумма двух чисел делится на 12, то сумма остатков от деления этих чисел на 12 также делится на 12, то есть равна 0 либо 12 (сумма двух цифр не может быт больше, чем 18). Поэтому заводим массив rem счётчиков чисел с одинаковыми остатками от деления на 12.
И при вводе очередного числа увеличиваем счётчик, соответствующий полученному остатку от деления на 12.
Подсчитываем общее количество пар. Если число делится на 12 (остаток 0), то оно образует пару со всеми числами, которые делятся на 12, кроме самого себя, таких сочетаний rem[0]*(rem[0]-1), но при этом каждая пара подсчитана дважды, то есть это произведение нужно разделить на 2. Аналогичная ситуация с теми числами, которые делятся на 6, количество соответствующих пар находим как
rem[6]*(rem[6]-1) div 2.
Для остальных подходящих пар остатки для двух чисел, образующих пару, не равны, так что каждое число из первой группы (например, с остатком 1) сочетается с каждым числом из второй группы (с остатком 12-1 = 11). Чтобы не получить дублирование пар, будем в цикле перебирать только остатки, меньшие 6.
117_old. На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии кратном 5 (разница в индексах элементов пары должна быть кратна 5, порядок элементов в паре неважен). Необходимо определить пару с максимальной суммой кратной 7. Если таких пар несколько, программа должна вывести любую из них.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
Программа должна вывести в первой строке два числа: пару элементов с максимальной суммой, находящихся в последовательности на расстоянии кратном 5, в которой сумма элементов кратна 7. Если ни одной подходящей пары нет, нужно вывести одно число 0.
Пример входных данных:
10
1
6
3
140
6
6
7
11
7
15
Пример выходных данных для приведённого выше примера входных данных:
7 140
Решение на 2 балла на языке Python:
a = []
m1 = -1
m2 = -1
n = int(input())
for i in range(n):
a.append( int(input()) )
for i in range(n-1):
for j in range(i+1,n):
if( (j-i) % 5 == 0 and (a[i]+a[j]) % 7 == 0 and
(a[i]+a[j]) > (m1+m2)):
m1 = a[i]
m2 = a[j]
if m1 == -1:
print(0)
else:
print(m1,m2)
Решение на 4 балла на языке Python:
#массив максимальных значений
a = []
for i in range(5):
a.append( [-1]*7 )
#Переменные для хранения искомой пары
m1 = -1
m2 = -1
n = int(input())
for i in range(n):
x = int(input())
k = i % 5
r = x % 7
r1 = (7 - r) % 7
if a[k][r1]!=-1 and (x+a[k][r1]) > (m1+m2):
m1 = x
m2 = a[k][r1]
if x > a[k][r]:
a[k][r] = x
if m1 == -1:
print(0)
else:
print(m1, m2)
Нас интересуют пары чисел на расстоянии кратном 5. Разобьём нашу последовательность на 5 частей, по остатку от деления индекса на 5. Поскольку у чисел в одной группе индексы будут иметь одинаковый остаток, разница между ними будет кратна 5.
Для каждой части создадим массив в котором будем хранить максимальные значения, притом в i ячейке массива будет храниться число, которое при делении на 7 даёт остаток i.
Для удобства для записи максимальных значений будем использовать двумерный массив. Строки будут означать остаток от деления индекса на 5, а столбцы – остаток от деления значения числа на 7.
Рассматриваемые пары состоят из 2 чисел: входное число и элемент массива, такой что номер строки – остаток от деления индекса входного числа на 5, а номер столбца – дополняющий до кратного 7 остаток к входному числу.
Для каждого входящего числа x вычисляем k – остаток от деления индекса на 5, r – остаток от деления числа x на 7, r1 – дополнительный остаток, такой что r+r1 кратно 7.
Далее проверяем, что для числа x существует подходящее ему значение a и что их сумма максимальна. Если это так – записываем их в соответствующие переменные.
В конце цикла проверяем, если x больше соответствующего значения a, то записываем его в массив.
После проверки всех чисел выводим 0, если искомой пары не нашлось и саму пару при положительном исходе.