РЕШУ ЕГЭ — информатика

Задания

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

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

Максимальная оценка за правильную программу, эффективную только по времени или только по памяти,  — 3 балла.

Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,  — 2 балла.

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

Описание входных и выходных данных:

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно неотрицательное число, меньшее 1000.

Пример входных данных:

Пример выходных данных для приведённого примера входных данных:

У чисел заданного набора чаще всего  — по 2 раза  — встречаются суммы 4 и 6, в ответе выводится меньшая из них.

Решение. Наименьшая возможная сумма цифр числа в заданном диапазоне равна 0, наибольшая  — 27. Необходимо создать массив с индексами от 0 до 27 и использовать его для подсчёта встречающихся сумм. Использование массива не делает программу неэффективной по памяти, так как размер массива не зависит от N. Затем нужно найти значение максимального элемента этого массива и вывести его индекс. Ниже приведены реализующие описанный выше алгоритм программы на языке Паскаль (использована система программирования PascalABC) и языке Java (версия языка 5.0 или выше). Программы отличаются способом вычисления суммы цифр очередного числа: в программе на Паскале использован обычный цикл разложения числа на цифры десятичной записи, в программе на Java сумма вычисляется по формуле, учитывающей, что число содержит не более трёх цифр. Оба способа допустимы.

Далее последует пример кода, который работает за линейное время.

язык - PascalABC.

var      
  N: integer;     {количество чисел}     
  a: integer;     {очередное число}    
  s: integer;     {сумма цифр числа}     
  k: array [0..27] of integer; {подсчёт сумм}     
  imx: integer;   {самая частая сумма}    
  i: integer; 
begin     
  for i:=0 to 27 do k[i]:=0;    
  readln(N);    
  for i:=1 to N do begin         
    readln(a);        
    s := 0;         
    while a>0 do begin           
      s := s + a mod 10;             
      a := a div 10;         
    end;         
    k[s] := k[s]+1;     
  end;     
  imx := 0;     
  for i:=0 to 27 do begin         
    if k[i] > k[imx] then imx := i;
  end;  
  write(imx)
  end.

import java.util.Scanner;
 
public class P27A {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int k[] = new int[28];
		for (int i = 0; i < N; ++i) {
			int a = in.nextInt();
			int s = a / 100 + a / 10 % 10 + a % 10;
			++k[s];
		}
		int imx = 0;
		for (int i = 1; i < k.length; ++i) {
			if (k[i] > k[imx])
				imx = i;
		}
		System.out.print(imx);
	}
}

Примечание ненужно обрабатывать случай, когда k[i] = k[imx] так как тогда нам все равно нужно будет оставить значение imx неизменным.

Пример правильной, но неэффективной программы на языке Паскаль.

var   N: integer; {количество чисел}
  val: integer; {самая частая сумма}
  a: array [1..10000] 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 + a[i] div 100 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 := N+1;
  lenght := 0;
  val := a[1];
  for i := 1 to N do
   if a[i]=a[i+1] then
     lenght := lenght + 1
    else begin
    if lenght>max_lenght then begin
    max_lenght := lenght;
    val := a[i];
    end;
    lenght := 0;
    end;
  writeln(val);
end.

Критерии проверки:

Критерии оценивания выполнения задания	Баллы
Пояснения для проверяющих. 1. Задание Б является усложнением задания А. Если в качестве решения задания Б представлено решение задания А, то согласно приведённым ниже критериям его оценка будет такой же, как если бы это решение было представлено в качестве решения задания А. 2. Два задания (и, соответственно, возможность для экзаменуемого представить две программы) дают ученику возможность (при его желании) сначала написать менее сложное и менее эффективное решение (задание А), которое даёт ему право получить 2 балла, а затем приступить к поиску более эффективного решения. 3. Приведённые в п. 2.1–2.5 правила имеют целью избежать снижения оценки из-за того, что ученик перепутал обозначения заданий
Критерии оценивания задания А
При решении задачи A программа верно находит требуемую сумму для любых 6 пар исходных данных. Допускается до пяти синтаксических и приравненных к ним ошибок (см. критерии оценивания задания Б на 4 балла)	2
Не выполнены условия, позволяющие поставить 2 балла. Из описания алгоритма и общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи. Допускается любое количество «описок»	1
Не выполнены критерии, позволяющие поставить 1 или 2 балла	0
Максимальный балл для задания А	2

Критерии оценивания выполнения задания Б	Баллы
Программа правильно работает для любых соответствующих условию входных данных и при этом эффективна как по времени, так и по памяти, т.е. не используются массивы и другие структуры данных (в том числе стек рекурсивных вызовов), размер которых зависит от количества входных элементов, а время работы пропорционально этому количеству. Возможно использование массивов и динамических структур данных при условии, что в них в каждый момент времени хранится фиксированное количество элементов, требующих для хранения меньше 1Кб. Программа может содержать не более трёх синтаксических ошибок следующих видов: 1) пропущен или неверно указан знак пунктуации; 2) неверно написано или пропущено зарезервированное слово языка программирования; 3) не описана или неверно описана переменная; 4) применяется операция, недопустимая для соответствующего типа данных. К синтаксическим ошибкам приравнивается использование неверного типа данных. Если одна и та же ошибка встречается несколько раз, она считается за одну ошибку	4
Не выполнены условия, позволяющие поставить 4 балла. Программа в целом работает правильно для любых входных данных произвольного размера. Время работы пропорционально количеству введённых чисел; правильно указано, какие величины должны вычисляться по ходу чтения элементов последовательности чисел. Количество синтаксических ошибок («описок») указанных выше видов – не более пяти. Используемая память, возможно, зависит от количества прочитанных чисел (например, входные данные запоминаются в массиве, контейнере STL в C++ или другой структуре данных). Допускается ошибка при вводе и выводе данных, не влияющая на содержание решения. Программа может содержать не более пяти синтаксических и приравненных к ним ошибок, описанных в критериях на 4 балла. Кроме того, допускается наличие одной ошибки, принадлежащей к одному из следующих видов: 1) ошибка инициализации, в том числе отсутствие инициализации; 2) не выводится результат, равный 0, или вместо 0 выводится неверное значение; 3) допущен выход за границу массива; 4) используется знак “<” вместо “<=”, “or” вместо “and” и т.п.	3
Не выполнены условия, позволяющие поставить 3 или 4 балла. Программа работает в целом верно, эффективно или нет, например для решения задачи используется перебор всех возможных вариантов выбора элементов в парах. В реализации алгоритма допускается до трёх содержательных ошибок, допустимые виды ошибок перечислены в критериях на 3 балла. Количество синтаксических «описок» не должно быть более семи. Программа может быть неэффективна по времени, например все числа запоминаются в массиве и перебираются все возможные суммы, т.е., по сути, реализовано решение задачи А без ограничений на количество ввёденных пар	2
Не выполнены условия, позволяющие поставить 2, 3 или 4 балла. Из описания алгоритма или общей структуры программы видно, что экзаменуемый в целом правильно представляет путь решения задачи независимо от эффективности. При этом программа может быть представлена отдельными фрагментами, без ограничений на количество синтаксических и содержательных ошибок. 1 балл ставится также за решения, верные лишь в частных случаях	1
Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла	0
Максимальный балл для задания Б	4
Итоговый максимальный балл	4

Ключ