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

Автор:Даниил Орешников   Ограничение времени: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

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

Автор:Даниил Орешников   Ограничение времени: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

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

Автор:Олег Христенко   Ограничение времени: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

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

Автор:Даниил Орешников, Геннадий Короткевич   Ограничение времени: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 

Задача B1. Календарь на Альфе Центавра

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

Условие

На планете в системе Альфы Центавра год состоит из m месяцев, пронумерованных от 1 до m, а каждый месяц из d дней, пронумерованных от 1 до d. В свою очередь, неделя у поселенцев на этой планете состоит из w дней, проиндексированных строчными английскими буквами, от "a" до w-й буквы английского алфавита.

Первый день первого месяца первого года соответствует букве "a".

Требуется определить, какой букве будет соответствовать i-й день j-го месяца k-го года.

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

Первая строка ввода содержит три целых числа d, m и w.

Вторая строка ввода содержит три целых числа i, j и k.

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

Выведите одну строчную букву английского алфавита — какой букве соответствует i-й день j-го месяца k-го года.

Ограничения

1 ≤ d, m ≤ 100, 1 ≤ w ≤ 26

1 ≤ i ≤ d, 1 ≤ j ≤ m, 1 ≤ k ≤ 109

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

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
116d = 1, m = 1первая ошибка
216m = 1, k ≤ 107 1первая ошибка
317i = 1, j = 1первая ошибка
417k = 1первая ошибка
517k ≤ 1004первая ошибка
617нет1 — 5первая ошибка

Замечание

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

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

Стандартный вход Стандартный выход
1
30 12 7
18 1 2021
b

Задача B2. Числа

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

Условие

Аня любит, когда числа состоят из одинаковых цифр. Поэтому ей нравятся числа 777 или 5555, а вот число 1234 ей совсем не нравится.

Иногда у Ани бывает хорошее настроение, тогда ей по прежнему нравятся все числа, состоящие из одинаковых цифр, но также нравятся числа, в которых все цифры кроме одной одинаковые, как, например, в числе 77727.

У Ани есть число x. Аня хочет найти минимальное целое число y ≥ x, которое ей понравится.

Требуется написать программу, которая по заданному целому числу x и информации, хорошее ли настроение у Ани, находит минимальное целое число y ≥ x, которое нравится Ане.

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

Первая строка ввода содержит целое число x (обратите внимание, что число x не может быть сохранено в стандартном 32-битном типе данных, необходимо использовать 64-битный тип данных, например long long в C++, int64 в Паскале).

Вторая строка ввода содержит число k, равное 0 или 1. Значение k = 1 означает, что у Ани хорошее настроение, а значение k = 0 — что это не так.

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

Следует вывести одно целое число y.

Должны выполняться следующие свойства:

Ограничения

1 ≤ x ≤ 1017

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

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
1151 ≤ x ≤ 105, k = 0полная
2201 ≤ x ≤ 1017, k = 01первая ошибка
3211 ≤ x ≤ 105, k = 0 или k = 11полная
4441 ≤ x ≤ 1017, k = 0 или k = 11 − 3первая ошибка

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

Стандартный вход Стандартный выход
1
700
0
777
2
700
1
700

Задача B3. Хорошие раскраски

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

Условие

Назовем раскраску клеток таблицы n × m хорошей, если никакие четыре клетки, центры которых образуют вершины прямоугольника со сторонами, параллельными осям координат, не покрашены в один цвет.

Иначе говоря, для раскраски не должно быть такой четверки целых чисел x1, x2, y1, y2, что 1 ≤ x1 < x2 ≤ n, 1 ≤ y1 < y2 ≤ m, и клетки (x1, y1), (x2, y1), (x1, y2) и (x2, y2) покрашены в одинаковый цвет.

Требуется написать программу, которая по заданным целым числам n, m и c находит любую хорошую раскраску таблицы n × m в c цветов.

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

В первой строке записаны три целых числа n, m, c.

Гарантируется, что для заданных во входных данных значений существует хотя бы одна хорошая раскраска.

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

Выведите n строк по m чисел в каждой.

В качестве j-го числа i-й строки выведите ai,j — цвет клетки (i,j) (1 ≤ ai,j ≤ c).

Если есть несколько хороших раскрасок, можно вывести любую из них.

Ограничения

2 ≤ n, m ≤ 10, 2 ≤ c ≤ 3

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

Кроме теста из примера в этой задаче 20 тестов, каждый независимо оценивается в 5 баллов. Среди этих тестов в пяти тестах c = 2 и в пятнадцати тестах c = 3.

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

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

Стандартный вход Стандартный выход
1
2 2 2
1 2 
2 2 

Задача B4. A+B

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

Условие

Рассмотрим a, b и c — целые неотрицательные числа, записанные в десятичной системе счисления. Пусть они имеют одинаковую длину n, при этом запись может начинаться с нуля. Числа записаны одно под другим, цифры расположены в три строки и n столбцов. Рассмотрим пример такой записи:


  01211
  12099
  23300
  

Требуется переставить столбцы в этой записи таким образом, чтобы выполнялось равенство a + b = c. В полученной записи ведущие нули уже запрещены. Сколько существует различных способов это сделать?

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

Поскольку ответ может быть довольно большим, требуется посчитать для него остаток по модулю 109 + 7.

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

Во входных данных записаны целые неотрицательные числа a, b и c по одному в строке. Каждое число состоит из n десятичных цифр и может начинаться с нуля.

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

Выведите количество подходящих перестановок столбцов по модулю 109 + 7.

Ограничения

2 ≤ n ≤ 2 ⋅ 105

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

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

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
172 ≤ n ≤ 6первая ошибка
2142 ≤ n ≤ 181первая ошибка
3152 ≤ n ≤ 200, нет цифры нольпервая ошибка
452 ≤ n ≤ 2001–3первая ошибка
5172 ≤ n ≤ 750, нет цифры ноль3первая ошибка
652 ≤ n ≤ 7501–5первая ошибка
7202 ≤ n ≤ 2 ⋅ 105, нет цифры ноль3, 5первая ошибка
8172 ≤ n ≤ 2 ⋅ 1051–7первая ошибка

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

В первом примере подходят все перестановки столбцов.

Во втором примере единственная подходящая перестановка — 10 + 20 = 30. 01 + 02 = 03 не считается из-за наличия ведущих нулей.

В третьем примере возможны варианты 10121 + 21909 = 32030 и 12101 + 20919 = 33020, причём каждый из них может быть получен двумя разными перестановками.

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

Стандартный вход Стандартный выход
1
123
123
246
6
2
01
02
03
1
3
01211
12099
23300
4
4
121
214
999
0

Задача C0. Дерево

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб
Максимальный балл:1  

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

Формат входного файла

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа ui и vi через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

Формат выходного файла

В первой строке выходного файла выведите YES, если граф является деревом, и NO в противном случае.

Ограничения

1 ≤ n ≤ 105

0 ≤ m ≤ 105

1 ≤ ui, vi ≤ n

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
1 3
YES
2
3 3
1 2
2 3
3 1
NO

Задача C1. Заморозки в Невеции

Автор:А. Щуров   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

В Невеции ударили морозы, и скоро водные каналы станут ледяными. Физики Невеции обнаружили, что каналы замерзают на один метр в сутки по ширине с каждой стороны, становясь таким образом с каждым днем всё ́́уже.

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

Формат входного файла

Входные данные содержат целые числа N, M и W — количество точек города, количество каналов и ширина лодок. Далее следуют M троек целых чисел ai bi wi — точки, которые соединяет канал, и его ширина. Каждый канал описывается ровно один раз.

Формат выходного файла

Выходные данные должны содержать одно целое число.

Ограничения

2 ≤ N ≤ 103

1 ≤ ai, bi ≤ N

1 ≤ M ≤ N(N − 1)2

1 ≤ wi, W ≤ 109

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
NMwi
1152 ≤ N ≤ 102M = N − 1wi ≤ 103полная
2152 ≤ N ≤ 102M ≤ N(N − 1)2wi ≤ 1031полная
3152 ≤ N ≤ 102M ≤ N(N − 1)2wi ≤ 1091, 2полная
4552 ≤ N ≤ 103M ≤ N(N − 1)2wi ≤ 1091, 2, 3полная

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3 5
1 2 15
2 3 11
3 4 20
4
2
2 1 1
1 2 3
2
3
3 3 10
1 2 9
1 3 10
2 3 10
1

Задача C2. Скалолаз

Автор:Иван Кобец   Ограничение времени:3 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Артем с раннего детства увлекается скалолазанием. Сегодня он решил покорить крупный горный хребет в своем городе.

Горный хребет представлен прямоугольником размером h × w метров. Каждая гора на этом хребте занимает квадрат 1 × 1 метр. Гора с координатами (x; y) имеет высоту hy,x метров. Чтобы перебираться между горами, Артём использует канат. Для того, чтобы перебраться с горы x,y на гору i,j, длина каната должна быть большей или равной разнице высот двух гор.

Двигаться Артем может только на соседние по горизонтали или вертикали горы.

Артем будет стартовать с самой верхней левой горы. Он хочет узнать, какой минимальной длины нужен канат, чтобы перебраться с левой стороны на правую сторону (в любую точку). Он просит Вас написать программу, которая сообщит ему минимальную длину каната.

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

В первой строке записано два натуральных числа h и w — размеры горного хребта. В следующих h строках записано по w чисел hi, j — высоты гор.

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

Программа должна вывести одно число — минимальную длину каната, при помощи которого можно перейти с левой на правую сторону.

Ограничения

2 ≤ h, w ≤ 1000

1 ≤ hi, j ≤ 109

Система оценки и описание подзадач

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
hwhi, j
1202 ≤ h ≤ 32 ≤ w ≤ 31 ≤ hi, j ≤ 50полная
2302 ≤ h ≤ 1002 ≤ w ≤ 1001 ≤ hi, j ≤ 10001полная
3502 ≤ h ≤ 10002 ≤ w ≤ 10001 ≤ hi, j ≤ 1091, 2полная

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

Стандартный вход Стандартный выход
1
3 3
4 9 7
6 8 1
8 1 1
2

Задача C3. Оптимальное удаление

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

Условие

Дано дерево, состоящее из n вершин. Корнем дерева считается вершина под номером 1. Необходимо удалить одно ребро из дерева (образовав тем самым еще одно дерево с новым корнем) так, чтобы сумма расстояний от корня до всех вершин была минимально возможной. Напишите программу, которая определит эту сумму.

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

В первой строке записано целое число n - количество вершин в дереве.

В следующих n − 1 строках записано по два различных целых числа ai и bi - вершины дерева, которые соединены между собой.

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

Выведите одно целое число - минимально возможную сумму расстояний от корня до всех вершин.

Ограничения

2 ≤ n ≤ 105

1 ≤ ai, bi ≤ n

Система оценки и описание подзадач

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
n
1152 ≤ n ≤ 100полная
2252 ≤ n ≤ 10001полная
3602 ≤ n ≤ 1051, 2полная

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

Минимальную сумму расстояний от корня до всех вершин можно получить, удалив ребро между вершинами 4 и 9. Тогда сумма расстояний от корня до всех вершин первого дерева будет 14, а второго (с корнем в вершине 9) 1.

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

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

Задача C4. Слон Пахом и разработка RPG

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

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

  1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
  2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
  3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

С платформы на платформу можно перейти, только если платформы стыкуются между собой. Во время похождения по коридору игрок может повернуть платформу, на которой он находится, на 90 градусов и продолжить прохождение в любом направлении, или же оставить платформу нетронутой и пройти дальше.

Игрок появляется в левом верхнем углу лабиринта и должен пройти в правый нижний угол.

Слон Пахом сгенерировал несколько лабиринтов, но теперь начал сомневаться в проходимости этих лабиринтов. Кроме того, Пахом считает, что поворот платформы запутывает игрока, поэтому для он хочет определить, можно ли пройти лабиринт, а если можно, то он хочет найти минимальное количество поворотов платформ, необходимое для прохождения лабиринта.

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

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

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

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

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

Если лабиринт проходимый, то следующая строка должна содержать целое число k — минимальное количество поворотов, необходимое для прохождения лабиринта.

Ограничения

1 ≤ n, m ≤ 103

Описание подзадач и системы оценивания

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

Стандартный вход Стандартный выход
1
5 5
+++++
+++++
+++++
+++++
+++++
YES
0
2
1 8
+-------
YES
0
3
1 8
+------|
NO
4
5 6
|-----
|-###-
#|---#
####|#
+++#|-
YES
5
5
1 1
#
NO

Задача D1. Марфа Геннадьевна в столовой

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит ci рублей. Для каждого блюда известен также коэффициент сытости блюда — ai.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

Формат входного файла

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел ci ai.

Формат выходного файла

Выходной файл должен содержать минимальную сумму денег, которую нужно потратить, чтобы наесться.

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ ci ≤ 500

1 ≤ ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 10
2 1
5 4
6 6
11
2
4 32
1 8
2 4
3 2
4 1
4

Задача D2. Бег по коридору

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору". По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром. Игрок может перемещаться в один из смежных пикселей, не занятых препятствием (смежными называются пиксели, соседствующие либо в строке, либо в столбце).

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

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

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

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
..
.#
1
2
6
....X.
#XXX..
3

Задача D3. Не только динамика! Новые тесты!

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб
Максимальный балл:1  

Условие

Дан набор ai из N чисел. Необходимо расположить числа в последовательности a1, a2, …, aN один за другим так, чтобы максимизировать следующую целевую функцию: (a1 * a2 + a2 * a3 + …  + aN − 1 * aN)

Формат входного файла

Входной файл содержит N, за которым следует N чисел ai.

Формат выходного файла

В выходном файле единственное число - максимальное значение целевой функции.

Ограничения

2 ≤ N ≤ 16

1 ≤ ai ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
9 1 9 2
108

0.997s 0.014s 47