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


Задания
Версия для печати и копирования в 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 Все