Инструкция по решению заданий: Присылайте исходный код, скомпилированный вариант и строку запуска программы. Все программы будут перекомпилированы на платформе Windows 7 по указанию участника (просьба указать в письме) и запускаться в консольном режиме на данной платформе.
Ответы принимаются сегодня в понедельник 9 декабря с 18:00 до 21:00 по Московскому времени по адресу olimp@relex.ru. Подведение итогов и награждение победителей состоится 13 декабря в 16:00 в конференц-зале главного учебного корпуса ВГУ на пленарном заседании Международной научной конференции «Актуальные проблемы прикладной математики, информатики и механики».Задача 1. «Ошибки не пройдут»
Введение
Команда программистов для тестирования важного проекта написала набор тестов. Из-за большого времени выполнения всех тестов и необходимости проверять каждое исправление было решено все тесты разбить на две группы: короткие по времени тесты и длинные. При большом количестве исправлений решено было проверять не все исправления индивидуально, а только выбранные с учетом ограниченного времени, выделенного для тестирования.
Постановка задачи
Необходимо определить количество проверенных исправлений и те исправления из N (N <= 100 000), которые будут не проверены в результаты запуска тестов. Известно, что короткий тест выполняется K1 секунд и берет себе каждую K2-ю по счету правку на проверку, длинный тест выполняется L1 секунд и берет себе каждую L2-ю по счету правку на проверку. В процессе выбора исправлений тесты просматривают все оставшиеся исправления по кругу. После того как тест запущен исправление исключается из списка просматриваемых. У короткого теста приоритет перед длинным, если они одновременно пытаются взять на проверку одну и ту же правку на проверку то она достается короткому тесту, а длинный берет следующую правку по порядку. На тестирование системы отводится M часов. Тестирование за пределами отведенного времени не допускается. Ограничение на время работы программы 10 секунд.
Исходные данные
С консоли в программу вводятся на первой строке N — количество исправлений, M — количество часов на проверку. На второй строке: K1, K2, L1, L2 — параметры короткого и длинного теста соответственно.
Выходные данные
Результаты работы программы должны выводиться на консоль в виде чисел на одной строке. Первое число — количество проверенных исправлений, остальные — номера непроверенных исправлений в порядке возрастания
Пример входных данных
10 1Пример выходных данных
8 6 10Задача 2. «Ну съешьте тортик!»
Введение
IT компания после успешной сдачи проектов устроила корпоративное праздничное мероприятие с веселыми конкурсами. В качестве одного из конкурсов предлагалось съесть как можно больше ну очень вкусных тортов. По правилам соревнований любой торт можно съесть одному или вместе с кем-нибудь для совместного веселья. Постоянных групп не было. В конце торжественного мероприятия организаторы попытались определить 3-х победителей и вручить им призы.
Постановка задачи
В конкурсе приняли участие за все время проведения мероприятия N (N<=20) человек. Известно какой торт в каком составе веселых участников был съеден. Считается, что каждый торт был поделен поровну между сидящими за одним столом. В процессе конкурса участникам разрешалось перемещаться между столами и образовывать разные группы. Победителем конкурса является группа из одного 1 или более человек, которые съели, сидя совместно, наибольшее количество тортов за все время проведения соревнований. Один человек мог стать победителем в составе нескольких групп. Ограничение на время работы программы 30 секунд.
Исходные данные
С консоли в программу вводятся на первой строке M (M <= 100 000) — количество съеденных тортов и N (N <= 20) — количество участников конкурса. Следующие M строк содержат: Mi — вес i-го торта в граммах, номера участников, которые съели этот торт.
Выходные данные
Результаты работы программы должны выводиться на консоль в виде 3-х строк. На i-ой строке выводится информация о занявших i-ое место: общий вес съеденных тортов в граммах и номера участников группы в отсортированном порядке.
Пример входных данных
6 5Пример выходных данных
2200 1 2
