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

Задания

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

Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

Задание А. Имеется набор чисел, состоящий из 10 пар положительных целых чисел. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.

Максимальная оценка за правильную программу – 2 балла.

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

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

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

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

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

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

В первой строке вводится одно целое положительное число  — количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D  — количество пришедших на очередной утренник детей, а затем K – количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений:

1 ≤ N ≤ 10000

1 ≤ D ≤ 100 (для каждого D)

D ≤ K ≤ 1000 (для каждой пары D, K)

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

Программа должна вывести одно число  — то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.

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

10 58

15 315

20 408

100 1000

32 63

11 121

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

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

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

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

program c4;

const DMAX=100; {максимально возможное количество детей}

var

N: integer; {количество утренников}

D: integer; {количество детей на утреннике}

K: integer; {количество конфет}

r: integer; {остаток}

c: array[1..DMAX-1] of integer; {счетчики остатков}

i: integer;

imax: integer;

begin

{предварительная очистка счетчиков}

for i:=1 to DMAX-1 do c[i]:=0;

readln(N);

{ввод данных, подсчет количества каждого остатка}

for i:=1 to N do begin

readln(D, K);

r := K mod D;

if r>0 then c[r]:=c[r]+1;

end;

{выбор самого частого остатка}

imax:=1;

for i:=2 to DMAX-1 do begin

if c[i]>=c[imax] then imax:=i;

end;

if c[imax]=0 then imax:=0;

writeln(imax);

end.

Пример решения задачи А на языке Паскаль.

var  D: integer; {количество детей на утреннике}
  K: integer; {количество конфет}
  r: array[1..10] of integer; {остатки}
  inf: array[1..10, 1..2] of integer; {исходные данные}
  val: integer; {самый частый остаток}
  max_lenght: integer;
  i, j, c, lenght: integer;
begin
  for i := 1 to 10 do begin
    read(D, K);
    inf[i, 1] := D;
    inf[i, 2] := K;
  end;
  for i := 1 to 10 do r[i] := inf[i, 2] mod inf[i, 1];
  for i := 1 to 10 do
    for j := 1 to 10-i do
      if r[j]      c := r[j];
      r[j] := r[j+1];
      r[j+1] := c;
    end;
  max_lenght := 0;
  lenght := 1;
  val := r[1];
  for i := 1 to 9 do
    if r[i]=r[i+1] then
      lenght := lenght + 1
    else begin
      if lenght>max_lenght then begin
        max_lenght := lenght;
        val := r[i];
      end;
      lenght := 1;
    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

Ключ