По новым правилам Московской командной олимпиады итоги олимпиады подводятся следующим образом.
Команды решают задачи и могут во время тура посылать их на проверку. Задача проверяется на системе тестов.
Каждая задача оценивается из 2-х баллов. 2 балла получает программа, которая проходит все тесты. Кроме того, 1 баллом оцениваются решения, которые проходят некоторое количество первых тестов в задаче (это количество определяется жюри, оно может быть различным в различных задачах, это количество, как и общее количество тестов по задаче, участникам не сообщается). Жюри может (однако не обязано) указать в условии дополнительные ограничения, которым удовлетворяют тесты, за прохождение которых ставится 1 балл.
Помимо баллов за решение задач, команды получают штрафное время. За каждую задачу штрафное время определяется следующим образом.
- Если за данную задачу у команды 0 баллов (независимо от того, делала команда попытки сдачи этой задачи или нет), штрафное время за эту задачу равно 0.
- Если у команды 1 балл за эту задачу, то штрафное время за задачу определяется как время в минутах от момента начала тура до момента, когда была сделана первая попытка, которая была оценена в 1 балл, плюс по 20 штрафных минут за каждую попытку по этой задаче, ей предшествовавшую. Заметьте, что все попытки, которые делаются после того, как команда получила 1 балл за задачу (но до того, как она получила 2 балла), не влияют на штрафное время и на баллы по задаче (даже если после этого будет сделана попытка, которая получит 0 баллов, 1 набранный балл у команды останется).
- Если у команды 2 балла за задачу, то штрафное время за эту задачу определяется как время в минутах от момента начала тура до момента, когда задача была сдана на 2 балла, плюс по 20 штрафных минут за каждую предшествовавшую неверную попытку по этой задаче (при этом неверными теперь считаются в том числе и попытки, получающие 1 балл). Заметьте, что все попытки, которые делаются после того, как команда решила задачу полностью, не влияют на штрафное время.
При этом если произошла ошибка компиляции программы, то такая попытка не учитывается при подсчете неверных попыток (то есть она вообще игнорируется).
Например, если на 1-й минуте команда послала программу, которая набрала 0 баллов, то штрафное время равно 0. Пусть на 2-й минуте команда послала решение, которое набрало 1 балл, тогда команда имеет за эту задачу 1 балл и штрафное время, равное 22 минутам (2 минуты от начала тура + 20 штрафных минут). Если на 3-й минуте команда сдала решение задачи на 2 балла, то результат по этой задаче у команды 2 балла, а штрафное время равно 43 минуты (3 минуты от начала тура + 2*20 минут за 2 предыдущие попытки).
И баллы, и штрафное время, полученное командой по разным задачам, суммируются (получаются суммарные баллы и суммарное штрафное время). Команды ранжируются сначала по баллам, а при равном количестве баллов — по штрафному времени (чем меньше штрафное время, тем выше место команды).
Напишите программу, которая по протоколу попыток, сделанных командой, вычисляет количество набранных командой баллов и штрафное время.
В первой строке задается число N — суммарное количество задач (1≤N
Далее идет M — количество сделанных командой попыток. Затем следуют M строк, каждая из которых содержит 3 числа: первое задает время в минутах от начала тура до момента совершения данной попытки, второе — номер задачи, третье — количество пройденных тестов (или –1, если произошла ошибка компиляции). Все попытки упорядочены по времени, ни в какую минуту команда не делала более одной попытки.
По правилам олимпиады общее количество попыток не превышает 200, продолжительность тура — 3-х месяцев (на самом деле, командная олимпиада длится обычно не более 5 часов, однако жюри олимпиады не исключает, что эти же правила когда-нибудь будут использоваться в заочном туре, который длится как раз 3 месяца).
Выведите два целых числа — количество набранных командой баллов и суммарное штрафное время.
1 20 10 3 1 1 0 2 1 10 3 1 20
2 43
2 17 24 2 2 2 5 1 1 8 2 -1
0 0
В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.
Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал, робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).
Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).
Оценка задачи
1 балл получат программы, правильно решающие задачу в случае, когда встреча роботов произойдет в зале, при ограничениях N≤100, K≤2000, M≤100.
4 5 1 2 2 3 3 4 1 4 1 3 3 1 2 4
1
3 2 1 2 2 3 2 1 3
1
Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.
Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.
Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.
1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.
Требуется вывести массив после сортировки.
4 1 4 2 3 2 4 3 1 2
1 2 4 3
В парикмахерской работают три мастера. Каждый тратит на одного клиента ровно полчаса, а затем сразу переходит к следующему, если в очереди кто-то есть, либо ожидает, когда придет следующий клиент.
Даны времена прихода клиентов в парикмахерскую (в том порядке, в котором они приходили). Требуется для каждого клиента указать время, когда он выйдет из парикмахерской.
В первой строке вводится натуральное число N, не превышающее 100 – количество клиентов.
Гарантируется, что всех клиентов успеют обслужить до полуночи.
Требуется вывести N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-го клиента (часы и минуты).
3 10 0 10 1 10 2
10 30 10 31 10 32
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).
Вводится число N — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:
- если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K≥1),
- если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K≥1).
Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.
Если выстроить вагоны по порядку невозможно, выведите одно число 0.
Примеры
| Входные данные | Выходные данные |
| 3 3 2 1 | 1 3 2 3 |
| 4 4 1 3 2 | 1 2 2 1 1 2 2 3 |
| 3 2 3 1 | 0 |