Дан набор из N целых положительных чисел. Для каждого числа вычисляется сумма двух последних цифр в его десятичной записи (для однозначных чисел предпоследняя цифра считается равной нулю). Необходимо определить, какая сумма при этом получается реже всего (но не менее одного раза). Если таких сумм несколько, необходимо вывести наименьшую из них.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бóльшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
Пример входных данных:
5
14
417
123
3
4841
Пример выходных данных для приведённого выше примера входных данных:
3
Суммы двух последних цифр для чисел из данного набора равны 5, 8, 5, 3, 5.
Реже других (по одному разу) встречаются 8 и 3, в ответе выводится меньшая из этих сумм.
Сумма двух цифр может принимать значения от 0 до 18. Необходимо создать массив из 19 элементов с индексами от 0 до 18 и использовать его для подсчёта количества чисел с соответствующими суммами двух последних цифр. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение минимального ненулевого элемента этого массива и вывести минимальный из индексов элементов, равных этому минимуму.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
var
N: integer; {количество чисел}
a: integer; {очередное число}
s: integer; {сумма двух последних цифр}
d: array [0..18] of integer; {подсчёт сумм}
mn: integer; {максимальное количество сумм}
imn: 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;
mn := N+1;
for i:=0 to 18 do begin
if (d[i]>0) and (d[i] < mn) then begin
mn := d[i];
imn := i;
end;
writeln(imn)
end.
Возможно также «лобовое» решение: запишем все исходные числа в массив, найдём суммы двух последних цифр этих чисел и отсортируем их в порядке возрастания, после чего найдём сумму, которая встречается реже всего. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество действий и время счёта с ростом количества исходных элементов растёт квадратично). Такая программа оценивается не выше двух баллов.
Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример правильной, но неэффективной программы на языке Паскаль
var
N: integer; {количество чисел}
val: integer; {самая редкая сумма}
a: array [1..1000] of integer;
min_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;
min_lenght := N+1;
lenght := 0;
val := a[1];
for i := 1 to N do
if a[i]=a[i+1] then
lenght := lenght + 1
else if lenght < min_lenght then begin
min_lenght := lenght;
val := a[i];
lenght := 0;
end;
writeln(val);
end.
Приводим эффективное решение Николая Артюхина на C++.
#include <iostream>
using namespace std;
int main()
{
int a[19], n, x, k=0, min=1001, ims, sum = 0;
cin >> n;
for(int i=0;i<19;i++){
a[i]=0;
}
for(int i=0;i<n;i++){
cin >> x;
sum= x%10 + (x/10)%10;
a[sum]++;
}
for(int i=0;i<19;i++){
if((a[i]<min)&&(a[i]>0)){
min=a[i];
ims=i;
}
}
cout << ims;
return 0;
}
