СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 27 № 6792

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 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)

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

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

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

7

10 58

15 315

20 408

100 1000

32 63

32 63

11 121

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

31

Решение.

Поскольку количество детей не превышает 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.


Аналоги к заданию № 6792: 6824 Все