Question

PASCALABCNET Дан набор из N целых положительных чисел. Для каждого числа вычисляется сумма двух последних цифр в его десятичной записи (для однозначных чисел предпоследняя цифра считается равной нулю). Необходимо определить, какая сумма при этом получается чаще всего. Если таких сумм несколько, необходимо вывести наибольшую из них. Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.

Answer 1

Var a:array[1..18] of integer;
s,i,x,n:integer;
begin
for i:=1 to 18 do a[i]:=0;
readln(n);
for i:=1 to n do begin
readln(x);
s:=x mod 10;
x:=x div 10;
s:=(x mod 10)+s;
a[s]:=a[s]+1;
end;
s:=1;
for i:=2 to 18 do if a[i]>=a[s] then s:=i;
writeln(s);
end.

Answer 2

Для решения этой задачи можно использовать массив для подсчета количества встречающихся сумм двух последних цифр исходных чисел. Так как сумма двух последних цифр не превышает 18, то достаточно объявить массив размером 19.

Для каждого числа из входных данных можно вычислить сумму двух последних цифр с помощью деления числа на 10 по модулю 100. Затем инкрементировать соответствующий элемент массива.

После этого можно пройти по массиву и найти наиболее часто встречающуюся сумму двух последних цифр. Если таких сумм несколько, то можно выбрать наибольшую из них, пройдя по массиву в обратном порядке.

Временная сложность такой программы будет O(N), так как мы проходим по массиву размером 19 только один раз. Память, используемая программой, также будет O(1), так как используется только один массив фиксированного размера.

Пример кода на языке PascalABC.NET:

lessCopy code
var
  n, i, sum, maxSum, maxCount: integer;
  count: array[0..18] of integer;
begin
  // чтение входных данных
  readln(n);
  
  // инициализация массива
  for i := 0 to 18 do
    count[i] := 0;
  
  // обработка каждого числа
  for i := 1 to n do
  begin
    readln(sum);
    sum := (sum mod 100) div 10 + (sum mod 10); // вычисление суммы двух последних цифр
    inc(count[sum]); // увеличение счетчика
  end;
  
  // поиск наиболее часто встречающейся суммы
  maxSum := 0;
  maxCount := 0;
  for i := 0 to 18 do
    if count[i] > maxCount then
    begin
      maxCount := count[i];
      maxSum := i;
    end;
  
  // вывод результата
  writeln(maxSum);
end.