Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
casting.in
Ограничение памяти:
256 Мб
Выходной файл:
casting.out
Максимальный балл:
102
Условие
В театре работает n актеров. Известно, что среди них a — высоких, b — голубоглазых и c — блондинов.
Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин.
Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать,
какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.
Требуется написать программу, которая по заданным числам n, a, b и c определяет
минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.
Пояснения к примерам
В первом примере, поскольку высоких актеров всего трое, то на главную роль не может подойти больше трех человек.
Во втором примере все актеры — блондины и все, кроме одного, — голубоглазые.
Тогда среди трех высоких актеров найдутся хотя бы два голубоглазых (и, естественно, они будут блондинами).
Следовательно, минимум два актера точно подойдут на главную роль в новом спектакле.
Система оценивания
Правильные решения для тестов, в которых требуется найти минимальное количество актеров, будут оцениваться из 50 баллов.
Правильные решения для тестов, в которых требуется найти максимальное количество актеров, будут оцениваться из 50 баллов.
Формат входного файла
Первая строка входного файла содержит одно число, которое задает, минимальное или максимальное количество актеров необходимо найти в данном тесте.
Это число может принимать следующие значения:
1, если в данном тесте требуется определить минимальное количество актеров
2, если в данном тесте требуется определить максимальное количество актеров
Вторая строка входного файла содержит разделенные пробелами четыре целых числа: nabc.
Формат выходного файла
Выходной файл должен содержать одно число — минимальное или максимальное (в зависимости от входных данных) количество актеров,
которые могут претендовать на главную роль в новом спектакле.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
table.in
Ограничение памяти:
256 Мб
Выходной файл:
table.out
Максимальный балл:
102
Условие
Возрождая древние традиции английских рыцарей, в одном городе члены школьного клуба
любителей информатики каждую неделю собираются за круглым столом и обсуждают результаты последних соревнований.
Руководитель клуба Иван Петрович недавно заметил, что не все ребята активно участвуют в обсуждении.
Понаблюдав за несколькими заседаниями клуба, он заметил, что активность члена клуба зависит от того,
кто с кем сидит рядом.
В клуб приходят на занятия m мальчиков и n девочек. Иван Петрович заметил, что мальчик
активно участвует в обсуждении только тогда, когда непосредственно рядом с ним
с обеих сторон от него сидят девочки, а девочка активно участвует в обсуждении только тогда,
когда непосредственно рядом с ней с одной стороны от нее сидит мальчик, а с другой — девочка.
Желая сделать заседание клуба как можно более интересным, Иван Петрович решил разместить
участников за круглым столом таким образом, чтобы как можно больше членов клуба приняло
активное участие в обсуждении.
Требуется написать программу, которая по заданным числам m и n выведет такой способ размещения
m мальчиков и n девочек за круглым столом, при котором максимальное количество членов клуба
будет активно участвовать в обсуждении.
Пояснения к примерам
В первом примере все члены клуба примут активное участие в обсуждении.
Во втором примере мальчики примут активное участие в обсуждении, а девочки нет.
В этом примере можно также разместить членов клуба следующим образом: «BBGG».
В этом случае активное участие в обсуждении примут обе девочки, а мальчики — нет.
Разместить всех так, чтобы три или четыре члена клуба приняли активное участие в обсуждении, нельзя.
Формат входного файла
Входной файл содержит два целых числа m и n, разделенных ровно одним пробелом.
Формат выходного файла
Выходной файл должен содержать строку с расположенными в некотором порядке m символами «B»
(заглавная латинская буква) и n символами «G» (заглавная латинская буква).
Символ «B» означает мальчика, а символ «G» — девочку.
Символы следует расположить в том порядке, в котором нужно разместить членов клуба вокруг стола.
Соседние символы соответствуют членам клуба, которые сидят рядом. Рядом сидят также члены клуба,
соответствующие первому и последнему символу выведенной строки.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
cond.in
Ограничение памяти:
256 Мб
Выходной файл:
cond.out
Максимальный балл:
102
Условие
При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.
Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна ai ватт.
Администрации школы предоставили список из m различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.
Пояснения к примерам
В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.
Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе — кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).
Система оценивания
Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.
Формат входного файла
Первая строка входного файла содержит одно целое число n — количество классов в школе.
Вторая строка содержит n целых чисел ai — минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.
Третья строка содержит одно целое число m — количество предложенных моделей кондиционеров.
Далее, в каждой из m строк содержится пара целых чисел bj и cj — мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.
Формат выходного файла
Выходной файл должен содержать одно число — минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
olympiad.in
Ограничение памяти:
256 Мб
Выходной файл:
olympiad.out
Максимальный балл:
102
Условие
На межрегиональной олимпиаде по программированию роботов соревнования проводятся в один тур и в необычном формате.
Задачи участникам раздаются последовательно, а не все в самом начале тура,
и каждая i-я задача становится доступной участникам в свой момент времени si.
При поступлении очередной задачи каждый участник должен сразу определить, будет он ее решать или нет.
В случае, если он выбирает для решения эту задачу, то у него есть ti минут на то, чтобы сдать ее решение на проверку,
причем в течение этого времени он не может переключиться на решение другой задачи.
Если же участник отказывается от решения этой задачи, то в будущем он не может к ней вернуться.
В тот момент, когда закончилось время, отведенное на задачу, которую решает участник,
он может начать решать другую задачу, ставшую доступной в этот же момент,
если такая задача есть, или ждать появления другой задачи.
При этом за правильное решение i-й задачи участник получает ci баллов.
Артур, представляющий на межрегиональной олимпиаде один из региональных центров искусственного интеллекта,
понимает, что важную роль на такой олимпиаде играет не только умение решать задачи,
но и правильный стратегический расчет того, какие задачи надо решать, а какие пропустить.
Ему, как и всем участникам, до начала тура известно, в какой момент времени каждая задача станет доступной,
сколько времени будет отведено на ее решение и сколько баллов можно получить за ее решение.
Артур является талантливым школьником и поэтому сможет успешно решить за отведенное время
и сдать на проверку любую задачу, которую он выберет для решения на олимпиаде.
Требуется написать программу, которая определяет, какое максимальное количество баллов
Артур сможет получить при оптимальном выборе задач, которые он будет решать, а также количество и перечень таких задач.
Пояснения к примерам
В первом примере Артур успевает решить все задачи и получить три балла.
Во втором примере Артуру выгоднее решать последнюю задачу и получить за нее три балла, чем решать только первые две и получить два балла.
Система оценивания
Частичные правильные решения для тестов, в которых все ci одинаковы и n ≤ 1000, оцениваются из 30 баллов.
Частичные правильные решения для тестов, в которых все ci одинаковы, оцениваются из 50 баллов.
Частичные правильные решения для тестов, в которых n ≤ 1000, оцениваются из 50 баллов.
Формат входного файла
Первая строка входного файла содержит одно целое число n — количество задач на олимпиаде.
Последующие n строк содержат описания задач, по три числа на каждой строке:
si — момент появления i-й задачи в минутах, ti — время, отведенное на ее решение в минутах,
и ci — сколько баллов получит участник за решение этой задачи.
Формат выходного файла
Первая строка выходного файл должна содержать одно число -– максимальное количество баллов, которое сможет получить Артур на олимпиаде.
Вторая строка должна содержать одно целое число m — количество задач, которые надо решить при оптимальном выборе.
Третья строка должна содержать m разделенных пробелом целых чисел — номера этих задач в порядке их решения.
Задачи пронумерованы, начиная с единицы, в порядке их описания во входном файле.
Если оптимальных ответов несколько, необходимо вывести любой из них.
Центральная предметно-методическая комиссия по информатике
Ограничение времени:
2 сек
Входной файл:
birch.in
Ограничение памяти:
512 Мб
Выходной файл:
birch.out
Максимальный балл:
102
Условие
На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной W метров. Вдоль левой стороны аллеи растет N берез,
а вдоль правой — M берез, при этом i-я береза с левой стороны аллеи находится на расстоянии ai метров от начала аллеи,
а j-я береза с правой стороны — на расстоянии bj метров от начала аллеи.
Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы.
Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой
(зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию).
К сожалению, в его распоряжении оказалась только лента длиной L метров, которую, к тому же, нельзя было разрезать.
Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез.
При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.
Требуется написать программу, которая по заданной длине ленты, ширине аллеи и положению берез на ней определяет максимальное количество берез,
которое можно окружить этой лентой. Считается, что березы представляются точками, толщиной берез и шириной ленты следует пренебречь.
Пояснения к примерам
В первом примере можно, например, оградить березы способом, указанным на рисунке.
Во втором примере длины ленты недостаточно, чтобы оградить хотя бы по одной березе с каждой стороны.
Система оценивания
Правильные решения для тестов, в которых 1 ≤ (N + M) ≤ 50, будут оцениваться из 30 баллов.
Правильные решения для тестов, в которых 1 ≤ (N + M) ≤ 500, будут оцениваться из 60 баллов.
Формат входного файла
Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты L и ширину аллеи W.
Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число N — количество берез,
а третья строка содержит N различных целых чисел a1, a2, …, aN, заданных по возрастанию.
Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число M — количество берез,
а пятая строка содержит M различных целых чисел b1, b2, …, bM, заданных по возрастанию.
Формат выходного файла
Выходной файл должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой.
Гарантируется, что если максимальное число берез, которое можно оградить лентой длины L, равно X, то нет способа оградить (X + 1) березу лентой длины (L + 10−5).
Ограничения
1 ≤ L ≤ 2×105; 1 ≤ W ≤ 104; 1 ≤ N, M ≤ 2000; 0 ≤ ai, bi ≤ 105;
Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы.
Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой
(зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию).
К сожалению, в его распоряжении оказалась только лента длиной L метров, которую, к тому же, нельзя было разрезать.
Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез.
При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.
Требуется написать программу, которая по заданной длине ленты, ширине аллеи и положению берез на ней определяет максимальное количество берез,
которое можно окружить этой лентой. Считается, что березы представляются точками, толщиной берез и шириной ленты следует пренебречь.
