Дан набор из N целых положительных чисел. Для каждого числа вычисляется сумма двух последних цифр в его десятичной записи (для однозначных чисел предпоследняя цифра считается равной нулю). Необходимо определить,
какая сумма при этом получается чаще всего. Если таких сумм несколько, необходимо вывести наибольшую из них.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается
не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой,итоговой станет бо́льшая из двух оценок. Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
Пример входных данных:
5
15
417
123
6
4841
Пример выходных данных для приведённого выше примера входных данных:
6
Суммы двух последних цифр для чисел из данного набора равны 6, 8, 5, 6, 5.
Чаще других (по два раза) встречаются 6 и 5, в ответе выводится бо́льшая из этих сумм.
Сумма двух цифр может принимать значения от 0 до 18. Необходимо создать массив из 19 элементов с индексами от 0 до 18 и использовать его для подсчёта количества чисел с соответствующими суммами двух последних цифр. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение максимального элемента этого массива и вывести максимальный из индексов элементов, равных этому максимуму.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC).
var
N: integer; {количество чисел}
a: integer; {очередное число}
s: integer; {сумма двух последних цифр}
d: array [0..18] of integer; {подсчёт сумм}
mx: integer; {максимальное количество сумм}
imx: integer; {самая частая сумма}
i: integer;
begin
for i:=0 to 18 do d[i]:=0;
readln(N);
for i:=1 to N do begin
readln(a);
s := a mod 10 + a div 10 mod 10;
d[s] := d[s]+1;
end;
mx := 0;
for i:=0 to 18 do begin
if d[i] >= mx then begin
mx := d[i];
imx := i;
end;
writeln(imx)
end.
Возможно также «лобовое» решение: запишем все исходные числа в массив, найдём суммы двух последних цифр этих чисел и отсортируем их в порядке убывания, после чего найдём сумму, которая встречается чаще всего. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше двух баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример правильной, но неэффективной программы на языке Паскаль
var
N: integer; {количество чисел}
val: integer; {самая частая сумма}
a: array [1..1000] of integer;
max_lenght: integer;
i, j, k, lenght: integer;
begin
readln(N);
for i:=1 to N do read(a[i]);
for i:=1 to N do a[i] := a[i] mod 10 + a[i] div 10 mod 10;
for i:=1 to N-1 do
for j:=1 to N-i do
if a[j] < a[j+1] then begin
k := a[j];
a[j] := a[j+1];
a[j+1] := k;
end;
max_lenght := 0;
lenght := 0;
val := a[1];
for i := 1 to N do
if a[i]=a[i+1] then
lenght := lenght + 1
else if lenght>max_lenght then begin
max_lenght := lenght;
val := a[i];
lenght := 0;
end;
writeln(val);
end.