Задача A. Табун ≡

Условие

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

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

Единственная строка входного файла содержит два натуральных числа, записанных через пробел: n и m — размер шахматной доски.

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

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n, m ≤ 10

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

Баллы за каждый тест начисляются независимо.

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

В примере на доске размером 2 × 4 какое бы место для себя не выбрал король, более 6 коней разместить нельзя. Одно поле останется пустым.

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

2 4

1

Задача B. Дважды два ≡

Условие

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

Считайте, что 1 ≤ a, b ≤ 9 и 0 ≤ n ≤ 99.

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

Три строки входного файла содержат два натуральных и одно целое неотрицательное числа: x, y и p. Первые два числа — множители, третье — их произведение, вычисленное по новым правилам. Гарантируется, что x × y ≠ p при обычном вычислении.

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

Выведите в трёх строках в том же формате три натуральных числа a, b и n — изменение в таблице умножения. Гарантируется, что во всех тестах такое изменение единственно (в общем случае это не так). Числа a и b выведите в порядке не убывания.

Ограничения

10 ≤ x, y ≤ 10⁹

0 ≤ p ≤ 10¹⁸

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

В примере в таблицу умножения было внесено изменение 3 × 4 = 15. Смотри рисунок: слева умножение по обычным правилам, справа — по новым. Красным цветом выделены изменившиеся цифры.

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

234
43
10365

3
4
15

Задача C. Снежки ≡

Условие

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

Первую кучку мальчик складывает так: нижний слой снежков в форме квадрата со стороной k, на него — слой снарядов со стороной k − 1, и так далее. На самом верху лежит один снежок.

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

На рисунке ниже Вы можете видеть первую кучку высотой 4 слоя (в ней 16 + 9 + 4 + 1 = 30 снежков) и вторую кучку высотой 5 слоёв (в ней 15 + 10 + 6 + 3 + 1 = 35 снежков).

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

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

Единственная строка входного файла содержит натуральное число n — количество снежков у Тимофея.

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

Выведите Yes или No — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10¹⁵

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

В первом примере дано n = 3. Разложить на две кучки невозможно.

Второй пример разобран в условии задачи.

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

3

No

65

Yes

Задача D. Часы ≡

Условие

После замены батарейки в электронных часах, Зинаиде требуется установить на индикаторе верное время. Для этого ей следует воспользоваться тремя кнопками, каждая из которых должна увеличивать число часов, минут и секунд на 1 соответственно. Однако, в последнее время эти кнопки барахлят — соответствующее число действительно увеличиваются на 1, зато два других на 1 уменьшаются! Например, если сейчас на индикаторе 12:34:56, то при нажатии на вторую кнопку время изменится на 11:35:55. Определите, какое минимальное количество нажатий на кнопки придётся сделать, чтобы установить нужное время.

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

Две строки входного файла содержат текущее и требуемое состояние индикатора в формате hh:mm:ss с ведущими нулями. Гарантируется, что эти два момента времени различны.

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

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

Ограничения

00 ≤ hh ≤ 23

00 ≤ mm, ss ≤ 59

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

Сейчас на индикаторе 00:00:00. Зинаида дважды нажмёт на вторую кнопку (время изменится сперва на 23:01:59, затем на 22:02:58) и один раз на третью.

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

00:00:00
21:01:59

3

Задача E. Подарочный массив ≡

Условие

У программиста Германа сегодня день рождения. Друзья решили сделать ему тематический подарок: они подарили ему массив длиной n, состоящий из двоичных цифр. Подарок Герману очень понравился и он сразу стал с ним экспериментировать.

Он придумал следующую операцию: выбирается некоторый отрезок от l до r включительно и все цифры на нём инвертируются (цифры 0 заменяются на 1, а цифры 1 заменяются на 0). Данную операцию он выполнил q раз. В процессе таких операций он записывал на листочек, сколько цифр 1 получилось в массиве после каждой инверсии. После всех операций он пошел спать.

На утро Герман понял, что забыл закрыть окно на ночь и листочек со всеми его записями улетел. Он помнит лишь последовательность операций. Исходя из них, он просит Вас написать программу, которая определит, какое максимальное количество единиц было в массиве после выполнения некоторой операции в последовательности.

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

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

Во второй строке записано n цифр a_i — двоичные цифры в массиве.

В третьей строке записано число q — количество операций, которое проделал Герман.

В следующих q строках записано по два положительных числа l и r — отрезки, массива к которым применялась операция.

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

Выведите одно число — максимальное количество единиц в массиве.

Ограничения

1 ≤ n, q ≤ 10⁵

0 ≤ a_i ≤ 1

1 ≤ l ≤ r ≤ n

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

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

3

Задача F. Импортозамещение ≡

Условие

Страна Битландия производит множество товаров. Соседняя страна Байтландия постоянно закупалась у Битландии.

Недавно в Байтландии произошла эпидемия, из-за которой нарушились каналы для поставки товаров. На восстановление уйдет много времени и денег.

Из-за этого Байтландия запустила тендер на закупку импортозамещающих товаров. Было определено k различных категорий товаров, которые пользуются спросом в стране. Каждая категория имеет свой код от 1 до k включительно. Свои товары предложили n различных компаний. Они заявили, какой тип товара предоставят, в каком количестве они его поставят и суммарную цену за всю поставку. По условиям тендера каждый товар может быть закуплен только у одной компании.

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

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

В первой строке заданы три натуральных числа n, k и s — количество заявок, количество категорий товаров и минимально необходимое общее количество товаров соответственно.

В следующих n строках записано по три натуральных числа t_i, a_i и c_i — код товара, количество товара и суммарную стоимость соответственно.

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

Выведите одно целое число — минимальную сумма, которую надо потратить на закупку. Если не закупку совершить невозможно, выведите -1.

Ограничения

1 ≤ n ≤ 10⁴

1 ≤ t_i ≤ k ≤ 100

1 ≤ a_i ≤ s ≤ 1000

1 ≤ c ≤ 100

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

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

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

7 5 8
3 2 9
4 2 4
4 4 7
3 2 2
2 4 2
1 4 10
4 3 7

8

Задача G. Делимая последовательность ≡

Условие

Дана последовательность a = [a₁, a₂, …, a_n], состоящая из n положительных целых чисел.

Требуется удалить несколько (возможно, ноль) чисел из последовательности таким образом, чтобы:

1. Наибольший общий делитель (НОД) всех чисел оставшихся чисел последовательности был больше 1.
2. Сумма удалённых чисел была минимально возможной.

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

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

Во второй строке задано n натуральных чисел a_i.

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

Выведите минимально возможную сумму удаляемых чисел.

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁴

1 ≤ a_i ≤ 10⁴

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

5
3 5 19 18 21

24

4
1 2 4 9

7

5
3 6 12 24 30

0

Задача H. Самурай ≡

Условие

Гонщик Саша на машине "Самурай 2" хочет побить рекорд времени на кольцевой трассе, составляющий M минут.

Длина трассы (1 круг) равна S км, машина может проехать без остановки на пит-стопе не более K км. Пит-стоп находится только в точке старта. Остановка на пит-стопе занимает T минут времени.

Сашина машина проехала ровно N кругов с постоянной скоростью V км в минуту.

Требуется определить, побил ли Саша рекорд, и вывести разницу между временем заезда Саши и рекорда.

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

Входные данные содержат целые числа M S K T V N.

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

Если Саша побил рекорд, нужно вывести YES, в ином случае NO. В следующей строке следует вывести разницу между рекордом и временем заезда Саши. Если при указанных данных нет возможности доехать до финиша, выведите  − 1 во второй строке.

Ограничения

1 ≤ M, S, K, T, V, N ≤ 10⁴;

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

10 5 9 1 4 4

YES
2.0

13 6 9 2 5 5

NO
1.0

Задача I. Упругие отскоки ≡

Условие

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

В начале эксперимента мяч находится в центре координат. Мяч кидают по направлению ненулевого вектора M с проекциями на оси M_x и M_y. Он движется с постоянной скоростью V м/c. Все удары абсолютно упругие (угол падения равен углу отражения, скорость мяча не меняется).

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

Гарантируется, что комната имеет вид прямоугольника, и что мяч в начале эксперимента находится внутри комнаты.

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

В первых четырех строках описываются координаты вершин комнаты в порядке против часовой стрелки: вещественные числа X_i и Y_i

Пятая строка содержит два вещественных числа M_x и M_y.

В шестой строке находятся целое и вещественное числа: V и t.

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

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

Ограничения

 − 1000 ≤ X_i, Y_i ≤ 1000

 − 1000 ≤ M_x, M_y ≤ 1000

0 < V ≤ 100

0 < t ≤ 10⁹

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

1 2
-1 2
-1 -2
1 -2
1 1
1 1

0.707107 0.707107

0 4
-3.2 -2.4
0 -4
3.2 2.4
1 2
1 4

1.41115 2.82229

Задача J. Без двух единиц подряд ≡

Условие

Артём и Женя играют в следующую игру: они по очереди называют натуральные числа в порядке возрастания, которые в своей двоичной записи не имеют двух единиц подряд. Такими числами, например, будут 1, 2, 4, 5, 8 и так далее. А вот числа 3 = 11₂, 6 = 110₂ или 7 = 111₂ игроки пропускают.

Артём только что назвал число n. Какое число следует назвать Жене, чтобы продолжить игру?

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

Единственная строка входных данных содержит натуральное число n. Гарантируется, что в его двоичном представлении нет двух единиц подряд.

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10¹⁷

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

В примере дано n = 9 = 1001₂. Следующее число n + 1 = 10 = 1010₂ тоже не имеет двух единиц подряд в своей двоичной записи.

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

9

10