Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет.

Дед Мороз и Снегурочка приходят на детские утренники с мешком конфет. Дед Мороз делит конфеты поровну между всеми присутствующими детьми (детей на утреннике никогда не бывает больше 100), а оставшиеся конфеты отдает Снегурочке. Снегурочка каждый раз записывает в блокнот количество полученных конфет. Если конфеты разделились между всеми детьми без остатка, Снегурочка ничего не получает и ничего не записывает. Когда утренники закончились, Деду Морозу стало интересно, какое число чаще всего записывала Снегурочка. Дед Мороз и Снегурочка — волшебные, поэтому число утренников N, на которых они побывали, может быть очень большим. Напишите программу, которая будет решать эту задачу. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Задание А. Имеется набор чисел, состоящий из 10 пар положительных целых чисел. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.Максимальная оценка за правильную программу - 2 балла. Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел. Постарайтесь сделать программу эффективной по времени и используемой памяти (или хотя бы по одной из этих характеристик).Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.Максимальная оценка за правильную программу, эффективную по времени и памяти, — 4 балла.Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла. Описание входных данныхВ первой строке вводится одно целое положительное число — количество утренников N. Каждая из следующих N строк содержит два целых числа: сначала D — количество пришедших на очередной утренник детей, а затем K - количество конфет в мешке Деда Мороза на этом утреннике. Гарантируется выполнение следующих соотношений:1 ≤ N ≤ 100001 ≤ D ≤ 100 (для каждого D)D ≤ K ≤ 1000 (для каждой пары D, K)Описание выходных данныхПрограмма должна вывести одно число — то, которое Снегурочка записывала чаще всего. Если несколько чисел записывались одинаково часто, надо вывести большее из них. Если Снегурочка ни разу ничего не записывала, надо вывести ноль.Пример входных данных:710 5815 31520 408100 100032 6332 6311 121Пример выходных данных для приведённого выше примера входных данных:31 Критерии оценивания выполнения задания | Баллы | Пояснения для проверяющих.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 |