Задача 1. Два станка

Автор:Даниил Орешников   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

На производстве имеется два станка. Необходимо изготовить как можно больше деталей за сегодняшнюю смену, продолжительность которой k минут.

Станки находятся в законсервированном состоянии. Для того, чтобы ввести в строй первый станок, требуется a минут, после чего он будет производить x деталей в минуту. Для того, чтобы ввести в строй второй станок, требуется b минут, после чего он будет производить y деталей в минуту.

Для введения в строй станка требуется присутствие инженера, поэтому нельзя вводить в строй два станка одновременно. При этом введение станка в строй и изготовление деталей на другом станке, а также одновременное изготовление деталей на двух станках разрешается.

Требуется выяснить, какое максимальное количество деталей удастся изготовить за k минут.

Формат входных данных

В первой строке ввода дано единственное целое неотрицательное число k — количество минут в смене.

Во второй строке ввода даны целые неотрицательные числа a и x — время введения первого станка в строй и количество деталей, которое он изготавливает за одну минуту.

В третьей строке ввода даны целые неотрицательные числа b и y — время введения второго станка в строй и количество деталей, которое он изготавливает за одну минуту.

Формат выходных данных

Выведите единственное число — максимальное количество деталей, которое удастся изготовить за смену.

Обратите внимание, что ответ в этой задаче может быть довольно большим и не помещаться в 32-битные типы данных. Рекомендуется использовать 64-битный тип данных, например long long в C++ или int64 в Паскале.

Ограничения

0 ≤ k ≤ 109, 0 ≤ a, x ≤ 109, 0 ≤ b, y ≤ 109

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
117a = 0, x = 0полная
214a = 0, b = 0полная
320a = b2первая ошибка
420x = yпервая ошибка
529нет1 — 4первая ошибка

Пояснение к примеру

В примере выгодно сначала ввести в строй второй станок и за оставшиеся 15 минут изготовить 45 деталей, а затем ввести в строй первый и за оставшиеся 5 минут изготовить на нём еще 20 деталей.

Если сначала ввести в строй первый станок и изготовить на нем в оставшиеся 10 минут 40 деталей, то после введения в строй второго на нем удастся изготовить лишь 15 деталей, суммарно 55, что меньше, чем 65.

Примеры тестов

Стандартный вход Стандартный выход
1
20
10 4
5 3
65

Задача 2. Разбиение таблицы

Автор:Даниил Орешников   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Рассмотрим таблицу из n строк и m столбцов, в клетки которой по строкам записаны числа от 1 до n ⋅ m. Сначала заполняется первая строка слева направо, затем вторая, и так далее. Другими словами в клетку (r, c) записано число (r − 1) ⋅ m + c.

На рисунке приведен пример такой таблицы для n = 3, m = 5.

12345
678910
1112131415

Требуется разделить таблицу одним вертикальным или горизонтальным разрезом, проходящим по сторонам клеток, так чтобы сумма чисел в получившихся частях таблицы отличалась как можно меньше. В этой задаче в одном тесте вам придётся ответить на несколько запросов об оптимальном разрезании таблицы.

Формат входных данных

В первой строке ввода задано целое число t — количество запросов.

В следующих t строках заданы по два целых числа n, m.

Формат выходных данных

В t строках выведите ответы на запросы, по одному на строке.

Ответ на каждый запрос должен быть выведен в формате D x, где D — это "V", если нужно резать по вертикали, "H" — если по горизонтали, а x — номер столбца или строки, перед которым надо сделать разрез. Строки пронумерованы от 1 до n, столбцы пронумерованы от 1 до m.

Если правильных ответов несколько, то надо вывести вариант с вертикальным разрезом, если он есть, а если и после этого вариантов несколько, то из вариантов с различными x следует выбрать тот, в котором x меньше.

Ограничения

1 ≤ t ≤ 105, (1 ≤ n, m ≤ 109, 2 ≤ n ⋅ m ≤ 109)

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
120t = 1, 1 ≤ n, m ≤ 100полная
214t = 1, 1 ≤ n, m ≤ 2 0001первая ошибка
315t = 1, 1 ≤ n, m ≤ 1071, 2первая ошибка
4161 ≤ t ≤ 1 000, 1 ≤ n × m ≤ 10 0001первая ошибка
5151 ≤ t ≤ 100 000, n = 1, 1 ≤ m ≤ 109первая ошибка
6201 ≤ t ≤ 100 000, 1 ≤ n, m ≤ 1091 — 5первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
5
1 3
4 7
1 10
3 3
3 5
V 3
V 5
V 8
H 3
V 4

Задача 3. Изменённая ДНК

Автор:Олег Христенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Биологи обнаружили новый живой организм и решили изучить его ДНК. ДНК кодируется последовательностью символов "A", "G", "C" и "T".

Так как строка, кодирующая ДНК, часто очень длинная, для её хранения применяют RLE-кодирование. А именно, каждый блок, состоящий из двух или более идущих подряд одинаковых символов, заменяется на число, равное длине этого блока, после которого записывается соответствующий символ. Например, последовательность "AAAGGTCCA" в закодированной форме имеет вид "3A2GT2CA".

В результате экспериментов, проводимых в лаборатории, ДНК может мутировать. Каждая мутация — это либо удаление одного символа из последовательности, либо добавление одного символа, либо замена одного символа на другой.

Уходя вечером из лаборатории, учёный записал ДНК в закодированной форме. Когда он вернулся на работу утром, он обнаружил, что в ДНК произошла ровно одна мутация. Теперь ученых интересует, какая минимальная и максимальная длина может получиться у новой ДНК в закодированной форме.

Требуется по заданной ДНК в закодированной форме определить, какая мутация может привести к тому, что у новой ДНК будет закодированная форма минимальной возможной длины, а какая — к тому, что у новой ДНК будет закодированная форма максимальной возможной длины.

Формат входных данных

В единственной строке входа находится строка s, состоящая из цифр и букв "A", "G", "C" и "T" — закодированная ДНК.

Гарантируется, что это строка является корректной закодированной записью некоторой строки из символов "A", "G", "C" и "T".

Формат выходных данных

В первой строке выведите мутацию, после которой закодированная строка имеет минимальную длину. Выведите:

В следующей строке выведите мутацию, после которой закодированная строка имеет максимальную длину, в таком же формате.

Если подходящих ответов несколько, можно вывести любой из них.

Ограничения

Обозначим за n длину закодированной строки, а за L длину исходной строки.

1 ≤ n ≤ 105, 1 ≤ L ≤ 109

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
191 ≤ n ≤ L ≤ 10полная
2171 ≤ n ≤ 100, 1 ≤ L ≤ 1041первая ошибка
3211 ≤ n ≤ 1000, 1 ≤ L ≤ 1051, 2первая ошибка
4111 ≤ n ≤ 105, 1 ≤ L ≤ 1071--3первая ошибка
5421 ≤ n ≤ 105, 1 ≤ L ≤ 1091--4первая ошибка

Пояснение к примеру

Исходная последовательность имела вид "AAAAACAAAAACC".

Первая операция превращает её в последовательность "AAAAAAAAAAACC", которая кодируется как "11A2C". Эта закодированная последовательность имеет минимальную возможную для этого теста длину, равную 5.

Вторая операция превращает её в последовательность "AACAAACAAAAACC", которая кодируется как "2AC3AC5A2C". Эта закодированная последовательность имеет максимальную возможную для этого теста длину, равную 10.

Примеры тестов

Стандартный вход Стандартный выход
1
5AC5A2C
3 6 A
1 2 C

Задача 4. Антенна

Автор:Даниил Орешников, Геннадий Короткевич   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Для связи с Землёй членам экспедиции на Марс необходимо собрать антенну. Антенна в разобранном состоянии представляет собой n фрагментов, i-й фрагмент представляет собой штангу длиной si сантиметров, на которой закреплены mi перекладин. Каждый фрагмент содержит хотя бы одну перекладину.

У каждой штанги есть начало, в котором расположен штекер, и конец, в котором расположено гнездо. Любые две штанги можно последовательно соединить, присоединив начало одной к концу другой. Для каждой перекладины известно расстояние от начала её штанги в сантиметрах. Для i-го фрагмента это расстояние может быть от 0 до si, значение 0 означает, что перекладина находится непосредственно в начале штанги, значение si — что она находится непосредственно в конце штанги. Толщиной перекладин и размерами штекера и гнезда следует пренебречь.

На рисунке показаны три фрагмента антенны из первого примера и отмечены расстояния от начала штанги до перекладины.

Чтобы корректно собрать антенну, необходимо соединить в некотором порядке все n фрагментов, при этом расстояние между любыми двумя соседними перекладинами должно быть одинаковым.

На рисунке показан корректный способ соединить фрагменты в первом примере.

К сожалению, члены экспедиции забыли инструкцию по сборке антенны на Земле, а передать её на Марс не представляется возможным — ведь антенна ещё не собрана. Помогите исследователям!

Требуется определить, в каком порядке необходимо соединить фрагменты антенны, чтобы установить связь с Землей.

Формат входных данных

В первой строке дано одно число n — количество фрагментов.

Далее дано описание n фрагментов. В первой строке описания фрагмента даны два целых числа mi и si — количество перекладин и длина штанги в i-м фрагменте. В следующей строке даны mi целых чисел pi, j — позиции перекладин, pi, j равно расстоянию в сантиметрах от начала штанги до j-й перекладины на ней.

Формат выходных данных

Если собрать антенну указанным образом возможно, в первой строке выведите Yes, а во второй строке выведите перестановку чисел от 1 до n — номера фрагментов в порядке, в котором их следует соединить, начало каждого следующего фрагмента в этом порядке присоединяется к концу предыдущего фрагмента. Если существует несколько подходящих ответов, можно вывести любой из них.

Если собрать антенну невозможно, в единственной строке выведите No.

Ограничения

1 ≤ n ≤ 100 000, 1 ≤ mi ≤ 100 000, 0 ≤ si ≤ 109

0 ≤ pi, 1 < pi, 2 < … pi, mi ≤ si

Сумма всех mi не превышает 100 000.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
18n ≤ 8, mi = 1, si ≤ 100первая ошибка
28n ≤ 8, si ≤ 1001первая ошибка
321n ≤ 1 0001, 2первая ошибка
421mi > nпервая ошибка
521si ≤ 1001, 2первая ошибка
621нет1 — 5первая ошибка

Примеры тестов

Стандартный вход Стандартный выход
1
3
1 7
3
1 8
6
2 8
1 6
Yes
2 1 3 
2
1
1 7
5
Yes
1
3
1
3 10
2 5 9
No
4
3
1 5
3
1 3
3
1 6
3
No
5
4
1 5
0
1 0
0
1 3
3
1 0
0
Yes
3 2 4 1 

0.884s 0.195s 23