--->
7 задач
<---
Для подготовки к чемпионату мира по футболу 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.
Данная задача содержит три подзадачи. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(K = 1\); \(N \leq 100\); каждый претендент характеризуется своим баллом от 1 до \(N\).
Сумма значений \(N\) по всем тестовым наборам не превосходит 10 000, каждый претендент характеризуется своим баллом от 1 до \(10^9\).
Сумма значений \(N\) по всем тестовым наборам не превосходит 100 000, каждый претендент характеризуется своим баллом от 1 до \(N\).
Сумма значений \(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
В городе \(\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\)) и временем начала игры участника на этом автомате.
Данная задача содержит пять подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(M = 1\), \(1 \leq N \leq 100\), \(t_1\) лежит в пределах от 1 до 100.
Все \(t_i\) равны 1, \(N = M\).
Все \(t_i\) равны 1, \(N > M\).
Числа \(t_i\) лежат в пределах от 1 до 100, \(N = M\).
Числа \(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