--->
78 задач
<---
Источники
#3394
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2011,
Задача B
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Для подготовки к чемпионату мира по футболу 2018 года создается школа олимпийского резерва. В нее нужно зачислить \(M\) юношей 1994−1996 годов рождения. По результатам тестирования каждому из \(N\) претендентов был выставлен определенный балл, характеризующий его мастерство. Все претенденты набрали различные баллы. В составе школы олимпийского резерва хотелось бы иметь \(A\) учащихся 1994 г.р., \(B\) – 1995 г.р. и \(C\) – 1996 г.р. (\(A + B + C = M\)). При этом минимальный балл зачисленного юноши 1994 г.р. должен быть больше, чем минимальный балл зачисленного 1995 г.р., а минимальный балл зачисленного 1995 г.р. должен быть больше, чем минимальный балл зачисленного 1996 г.р. Все претенденты, набравшие балл больше минимального балла для юношей своего года рождения, также должны быть зачислены.
В базе данных для каждого претендента записаны год его рождения и тестовый балл. Требуется определить, сколько нужно зачислить юношей каждого года рождения \(M_{94}\), \(M_{95}\) и \(M_{96}\) (\(M_{94} + M_{95} + M_{96} = M\)), чтобы значение величины \(F = |M_{94} − A| + |M_{95} − B| + |M_{96} − C|\) было минимально, все правила, касающиеся минимальных баллов зачисленных, были соблюдены, и должен быть зачислен хотя бы один юноша каждого требуемого года рождения.
Входные данные
В первой строке входного файла находится число \(K\) – количество наборов входных данных. Далее следуют описания каждого из наборов. В начале каждого набора расположены три натуральных числа \(A\), \(B\), \(C\). Во второй строке описания находится число \(N\) – количество претендентов (гарантируется, что \(N \geq A + B + C\)). В каждой из следующих \(N\) строк набора содержатся два натуральных числа – год рождения (число 1994, 1995 или 1996 соответственно) и тестовый балл очередного претендента.
Выходные данные
Ответ на каждый тестовый набор выводится в отдельной строке. Если хотя бы одно из требований выполнить невозможно, то в качестве ответа следует вывести только число −1. В противном случае соответствующая строка сначала должна содержать минимальное значение величины \(F\), а затем три числа \(M_{94}\), \(M_{95}\) и \(M_{96}\), на которых это минимальное значение достигается, удовлетворяющие всем требованиям отбора. Если искомых вариантов несколько, то разрешается выводить любой из них.
Комментарий
В первом примере на первом наборе ответ не существует, потому что нельзя пригласить хотя бы одного юношу 1995 г.р. Во втором наборе ответ существует и единственный, в третьем – нельзя выполнить правило относительно минимальных баллов.
Во втором примере правильным является также ответ 2 2 2 2.
Подзадачи и система оценки
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
Подзадача 1 (25 баллов)
\(K = 1\); \(N \leq 100\); каждый претендент характеризуется своим баллом от 1 до \(N\).
Подзадача 2 (25 баллов)
Сумма значений \(N\) по всем тестовым наборам не превосходит 10 000, каждый претендент характеризуется своим баллом от 1 до \(10^9\).
Подзадача 3 (25 баллов)
Сумма значений \(N\) по всем тестовым наборам не превосходит 100 000, каждый претендент характеризуется своим баллом от 1 до \(N\).
Подзадача 4 (25 баллов)
Сумма значений \(N\) по всем тестовым наборам не превосходит 300 000, каждый претендент характеризуется своим баллом в диапазоне от 1 до \(10^9\).
Примеры
Входные данные
3 1 1 1 4 1994 3 1994 4 1996 1 1996 2 1 1 1 3 1995 2 1994 3 1996 1 1 1 1 3 1994 1 1995 2 1996 3
Выходные данные
-1 0 1 1 1 -1
Входные данные
1 2 3 1 7 1996 2 1994 7 1994 4 1996 1 1995 3 1994 5 1995 6
Выходные данные
2 3 2 1
#3397
Темы:
[Жадный алгоритм]
[Задачи на моделирование]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Заключительный этап,
2011,
Задача E
]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
В городе \(\pi\) недавно построили парк аттракционов, в котором есть павильон игровых автоматов. Каждый из автоматов рассчитан на одного человека. В программе Всероссийской олимпиады планируется посещение этого павильона.
Перед организаторами встала сложная задача — составить расписание игры участников олимпиады на автоматах таким образом, чтобы каждый из \(N\) участников олимпиады смог поиграть на каждом из автоматов, и при этом автобус, увозящий участников из парка олимпиады, смог бы отправиться к месту проживания как можно раньше.
Время перемещения участников между автоматами, а также между автобусом и павильоном считается равным нулю. Каждый из участников в любой момент времени может как играть на автомате, так и ждать своей очереди, например, гуляя по парку. Для каждого из \(M\) (\(M \leq N\)) автоматов известно время игры на нём \(t_i\) (\(1 \leq i \leq M\)). Прервать начатую игру на автомате невозможно. Автобус привозит всех участников олимпиады в парк одновременно в нулевой момент времени.
Требуется написать программу, которая по заданным числам \(N\), \(M\) и \(t_i\) определяет оптимальное расписание игры на автоматах для каждого из участников.
Входные данные
В первой строке входного файла содержатся два числа: \(N\) и \(M\) (\(1 \leq M \leq N \leq 100\)). Во второй строке заданы \(M\) целых чисел \(t_i\) (\(1 \leq t_i \leq 100\)), каждое из которых задаёт время игры на \(i\)-м автомате (\(1 \leq i \leq M\)). Числа в строке разделяются одиночными пробелами.
Выходные данные
В первой строке необходимо вывести одно число — минимально возможное время отправления автобуса из парка аттракционов. Далее необходимо вывести \(N\) расписаний игр на автоматах, по одному для каждого из участников. Каждое расписание описывается в (\(M + 1\)) строках, первая из которых — пустая, а далее следуют \(M\) строк, описывающих автоматы в порядке их посещения этим участником. Посещение автомата описывается двумя целыми числами: номером автомата \(j\) (\(1 \leq j \leq M\)) и временем начала игры участника на этом автомате.
Примеры тестов
Подзадачи и система оценки
Данная задача содержит пять подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
Подзадача 1 (20 баллов)
\(M = 1\), \(1 \leq N \leq 100\), \(t_1\) лежит в пределах от 1 до 100.
Подзадача 2 (20 баллов)
Все \(t_i\) равны 1, \(N = M\).
Подзадача 3 (20 баллов)
Все \(t_i\) равны 1, \(N > M\).
Подзадача 4 (20 баллов)
Числа \(t_i\) лежат в пределах от 1 до 100, \(N = M\).
Подзадача 5 (20 баллов)
Числа \(t_i\) лежат в пределах от 1 до 100, \(N > M\).
Примеры
Входные данные
2 1 2
Выходные данные
4 1 0 1 2
Входные данные
3 2 2 1
Выходные данные
6 1 0 2 2 1 2 2 4 2 0 1 4
#3402
Темы:
[Задачи на моделирование]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2007,
Задача A
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Недавно Петя начал играть в шахматы.
Напомним, что в шахматы играют два игрока, у каждого из которых изначально есть по 8 фигур и 8 пешек. В этой задаче пешки рассматривать не будем.
Ни одна фигура, кроме коня, не может перепрыгивать через свои или чужие фигуры. Нельзя делать ход на поле, занятое своей фигурой. При ходе на поле, занятое чужой фигурой, она снимается с доски.
Фигуры ходят следующим образом:
король - на любую соседнюю по вертикали, горизотнали или диагонали клетку;
ферзь - на любое расстояние по вертикали, горизонтали или диагонали;
ладья - на любое расстояние по вертикали или горизонтали;
слон - на любое расстояние по диагонали;
конь - в форме буквы "Г": на 1 клетку по горизонтали и на 2 по вертикали, или наоборот, на 1 клетку по вертикали и 2 по горизонтали.
Вам даны позиции одной белой и одной черной фигуры.
Определите, бьют ли фигуры друг друга, и, если бьют, выведите какая из них бьет какую.
Входные данные
Первая строка входного файла содержит тип и позицию белой фигуры. Вторая строка содержит тип и позицию черной фигуры.
Каждая фигура задается строкой, состоящей из трех символов. Первый символ обозначает тип фигуры:
B - слон, N - конь, R - ладья, Q - ферзь, K - король.
Второй символ задает горизонталь (от \(a\) до \(h\)). Третий символ задает вертикаль (от 1 до 8).
Гарантируется, что фигуры стоят на различных клетках шахматной доски.
Выходные данные
В выходной файл выведите одно слово - ответ на задачу.
В случае, если ни одна фигура не бьет другую, выведите "NONE".
В случае, если обе фигуры бьют друг друга, выведите "BOTH".
В случае, если белая фигура бьет черную, а черная не бьет белую, выведите "WHITE".
В случае, если черная фигура бьет белую, а белая не бьет черную, выведите "BLACK".
Примеры
Входные данные
Ka1 Rg1
Выходные данные
BLACK
Входные данные
Qf3 Qh5
Выходные данные
BOTH
#3404
Темы:
[Разбор выражений]
[Задачи на моделирование]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2007,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Ася Вуткина - известный футбольный комментатор. Будучи профессионалом своего дела, Ася тщательно следит за всеми матчами всех европейских чемпионатов.
Благодаря накопленной информации, Ася может во время трансляции матча сообщить какую-нибудь интересную статистику, например: "Индзаги третий матч подряд забивает гол на 9-й минуте" или "Матерацци никогда не открывает счет в матче".
Но мозг Аси не безграничен, а помнить всю историю футбола просто невозможно. Поэтому Ася попросила вас написать программу, которая собирает статистику матчей и умеет отвечать на некоторые запросы, касающиеся истории футбола.
Информация о матче сообщается программе в следующей форме:
"Название 1-й команды" - "Название 2-й команды" Счет 1-й команды:Счет 2-й команды
Автор 1-го забитого мяча 1-й команды Минута, на которой был забит мяч'
Автор 2-го забитого мяча 1-й команды Минута, на которой был забит мяч'
...
Автор последнего забитого мяча 1-й команды Минута, на которой был забит мяч'
Автор 1-го забитого мяча 2-й команды Минута, на которой был забит мяч'
...
Автор последнего забитого мяча 2-й команды> <Минута, на которой был забит мяч>'
Запросы к программе бывают следующих видов:
Total goals for Название команды
- количество голов, забитое данной командой за все матчи.
Mean goals per game for Название команды
- среднее количество голов, забиваемое данной командой за один матч. Гарантирутся, что к моменту подачи такого запроса команда уже сыграла хотя бы один матч.
Total goals by Имя игрока
- количество голов, забитое данным игроком за все матчи.
Mean goals per game by Имя игрока
- среднее количество голов, забиваемое данным игроком за один матч его команды. Гарантирутся, что к моменту подачи такого запроса игрок уже забил хотя бы один гол.
Goals on minute Минута by Имя игрока
- количество голов, забитых данным игроком ровно на указанной минуте матча.
\texttt{Goals on first <\(T\)> minutes by <Имя игрока>}\\ --- количество голов, забитых данным игроком на минутах с первой по \(T\)-ю включительно.Goals on last \(T\) minutes by Имя игрока
- количество голов, забитых данным игроком на минутах с \((91 - T)\)-й по 90-ю включительно.
Score opens by Название команды
- сколько раз данная команда открывала счет в матче.
Score opens by Имя игрока
- сколько раз данный игрок открывал счет в матче.
Входные данные
Входной файл содержит информацию о матчах и запросы в том порядке, в котором они поступают в программу Аси Вуткиной.
Во входном файле содержится информация не более чем о 100 матчах, в каждом из которых забито не более 10 голов. Всего в чемпионате участвует не более 20 команд, в каждой команде не более 10 игроков забивают голы.
Все названия команд и имена игроков состоят только из прописных и строчных латинских букв и пробелов, а их длина не превышает 30. Прописные и строчные буквы считаются различными. Имена и названия не начинаются и не оканчиваются пробелами и не содержат двух пробелов подряд. Каждое имя и название содержит хотя бы одну букву.
Минута, на которой забит гол - целое число от 1 до 90 (про голы, забитые в дополнительное время, принято говорить, что они забиты на 90-й минуте).
Для простоты будем считать, что голов в собственные ворота в европейских чемпионатах не забивают, и на одной минуте матча может быть забито не более одного гола (в том числе на 90-й). Во время чемпионата игроки не переходят из одного клуба в другой.
Количество запросов во входном файле не превышает 500.
Выходные данные
Для каждого запроса во входном файле выведите ответ на этот запрос в отдельной строке. Ответы на запросы, подразумевающие нецелочисленный ответ, должны быть верны с точностью до трех знаков после запятой.
Примеры
Входные данные
"Juventus" - "Milan" 3:1 Inzaghi 45' Del Piero 67' Del Piero 90' Shevchenko 34' Total goals for "Juventus" Total goals by Pagliuca Mean goals per game by Inzaghi "Juventus" - "Lazio" 0:0 Mean goals per game by Inzaghi Mean goals per game by Shevchenko Score opens by Inzaghi
Выходные данные
3 0 1.0 0.5 1.0 0
Входные данные
Total goals by Arshavin
Выходные данные
0
#3410
Темы:
[Задачи на моделирование]
Источники:
[
Командные олимпиады,
Командные чемпионаты школьников Санкт-Петербурга по программированию,
2007,
Задача I
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Петя и Вася играют в забавную игру с карточками. Игра очень простая. Есть колода карт, на каждой из которых написана буква латинского алфавита. Карты перемешиваются, выдаются участникам и они составляют из них слова.
Вася хочет немножко смухлевать. Он знает, в каком порядке лежат карты в колоде и как Петя их мешает. По этим данным он хочет узнать, как будут лежать карты после перемешивания.
Перемешивание карт происходит в несколько этапов. На каждом этапе Петя сначала по очереди берет карты из колоды от верхней к нижней и раскладывает их на две стопки: одну налево, одну направо, одну налево, одну направо. После этого он кладет левую стопку на правую. Эти действия повторяются k раз.
Помогите Васе определить, как будут лежать карты в колоде после перемешивания.
Входные данные
Первая строка входного файла содержит строку, описывающую состояние колоды до перемешивания. Строка состоит из заглавных латинских букв. i-я буква строки соответствует i-й карте от низа колоды. Длина строки не превышает 100 символов.
Вторая строка содержит целое число k (1 ≤ k ≤ 100).
Выходные данные
В выходной файл выведите состояние колоды после перемешивания в том же формате, что и во входном файле.
Примеры
Входные данные
ABCDEFG 1
Выходные данные
FDBGECA
Выбрано
:
|