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

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ k ≤ 10⁹, 0 ≤ a, x ≤ 10⁹, 0 ≤ b, y ≤ 10⁹

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

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

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

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

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

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

20
10 4
5 3

65

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ t ≤ 10⁵, (1 ≤ n, m ≤ 10⁹, 2 ≤ n ⋅ m ≤ 10⁹)

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

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

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

5
1 3
4 7
1 10
3 3
3 5

V 3
V 5
V 8
H 3
V 4

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

Условие

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

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

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

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

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

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

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

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

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

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

• 1 x Z, если надо вставить символ Z так, чтобы слева от него было ровно x старых символов. Символ Z должен быть из множества {A, C, G, T}.
• 2 x, если надо удалить символ с номером x из последовательности.
• 3 x Z, если надо заменить символ с номером x на символ Z. Символ Z должен быть из множества {A, C, G, T}. При этом на этом месте до мутации обязательно должен был находиться символ, не равный Z.

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

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

Ограничения

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

1 ≤ n ≤ 10⁵, 1 ≤ L ≤ 10⁹

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

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

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

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

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

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

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

5AC5A2C

3 6 A
1 2 C

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100 000, 1 ≤ m_i ≤ 100 000, 0 ≤ s_i ≤ 10⁹

0 ≤ p_{i, 1} < p_{i, 2} < …  < p_{i, mi} ≤ s_i

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

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

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

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

3
1 7
3
1 8
6
2 8
1 6

Yes
2 1 3 

1
1 7
5

Yes
1

1
3 10
2 5 9

No

3
1 5
3
1 3
3
1 6
3

No

4
1 5
0
1 0
0
1 3
3
1 0
0

Yes
3 2 4 1