Программирование

Анализ пар значений

Задане № 1

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

Решение:

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;

{Ввод количества утренников}
write(‘Введите количество утренников: ‘);
readln(N);

{ввод данных, подсчет количества каждого остатка}
for i:=1 to N do
begin
write(‘Введите ‘,i,’ пару: ‘);
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; // Если i элемент больше imax то i и imax меняем местами
end;

{выводим результат}
if c[imax]=0 then imax:=0;
writeln(‘____________________________________’);
writeln(‘Количество утренников: ‘,N);
writeln(‘Число которое чаще всего записывала Снегурочка: ‘, imax);
writeln(‘____________________________________’);
end.

Анализ результатов работы программы:

i D K K mod D (r) Массив счетчиков
1 11 22 0 Не меняется
2 33 44 11 c[11] увеличивается на 1
3 55 66 11 c[11] увеличивается на 1
Ответ 11 (так как число 11 встречается чаще всего)
i D K K mod D (r) Массив счетчиков
1 10 58 8 c[8] увеличивается на 1
2 15 315 0 Не меняется
3 20 408 8 c[8] увеличивается на 1
4 100 1000 0 Не меняется
5 32 63 31 c[31] увеличивается на 1
6 32 63 31 c[31] увеличивается на 1
7 11 121 0 Не меняется
Ответ 31 (так как число 31 встречается чаще всего и оно больше 8)