Задача A. Калькулятор ≡

Условие

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

Сначала пользователь вводит целое положительное число n, которое выводится на экран. Затем пользователь может нажимать на три кнопки: A, B и C.

При нажатии на кнопку A число, которое выведено на экран, делится на 2. Если число на экране нечетное, то остаток отбрасывается. Например, результат этой операции для числа 80 равен 40, а для числа 239 равен 119.

При нажатии на кнопку B к числу, которое выведено на экран, прибавляется 1, и результат делится на 2. Остаток от деления отбрасывается. Например, результат операции для числа 80 равен 40, а для числа 239 равен 120.

При нажатии на кнопку C происходит следующее. Если число, которое выведено на экран, положительное, то из него вычитается 1 и результат делится на 2, остаток отбрасывается. Если же перед нажатием на кнопку C на экран было выведено число 0, то оно остается неизменным. Например, результат операции для числа 80 равен 39, а для числа 239 равен 119.

Пользователь ввел число n и собирается нажать на кнопки операций в некотором порядке. В частности, он планирует нажать на кнопку A суммарно a раз, на кнопку B  — b раз и на кнопку C  — c раз. Его заинтересовал вопрос, какое минимальное число может получиться в результате выполнения описанных операций.

Требуется написать программу, которая по введенному числу n и числам a, b и c, показывающим количество произведенных на калькуляторе операций разного типа, определяет минимальное число, которое может получиться в результате работы калькулятора.

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

Входной файл содержит четыре целых числа: n, a, b и c. Числа заданы на одной строке, соседние числа разделены одним пробелом.

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

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

Ограничения

1 ≤ n ≤ 10¹⁸, 0 ≤ a, b, c ≤ 60

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

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

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

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

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

В примере пользователю необходимо оптимально действовать следующим образом: нажать на кнопку B и получить число 36, затем нажать на кнопку A и получить число 18, затем нажать на кнопку C и получить число 8, затем второй раз нажать на кнопку A и получить число 4.

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

72 2 1 1

4

Задача B. Профессор и песок ≡

Условие

Профессор одной из кафедр ДВФУ разработал инновационный метод для того, чтобы определять момента завершения лекции. У профессора есть двое песочных часов. В первых песок полностью пересыпается за a минут, во вторых — за b минут. В начале лекции весь песок в часах находится внизу и профессор переворачивает первые, вторые или сразу и те и другие часы. Как только песок в каких-нибудь часах полностью пересыпался, профессор может опять перевернуть первые, вторые или сразу и те и другие часы.

К концу лекции весь песок в часах вновь должен оказаться внизу. Лекция длится T минут.

По заданным a, b и T определите искомую последовательность переворотов.

Считается, что профессор переворачивает часы мгновенно.

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит количество тестов n. Далее следует n строк с целыми числами T, a, b.

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

Выходной файл должен содержать n блоков с ответами на тесты.

Первая строка каждого блока должна содержать количество действий, k. Далее должно следовать k строк с парами целых чисел t_i m_i в каждой, где t_i — время выполнения действия, m_i — одно из чисел 1, 2 или 3, обозначающее, что необходимо перевернуть первые, вторые или и те и другие часы соответственно. Для первого действия должно быть t_i = 0, для остальных t_i должно быть таким, что в этот момент песок хотя бы в одних часах только что полностью пересыпался вниз. Все t_i должны быть различны и расположены по возрастанию.

Для каждого теста выведите такой ответ, в котором количество действий не превосходит 500. Гарантируется, что в каждом тесте такой ответ существует.

Примечание: Поскольку блоки в выходном файле находятся один за другим, то, если указать неверное k в начале блока, все последующие блоки будут восприняты как ошибочные. Поэтому в случае частичного решения задачи рекомендуется указывать k = 0 для тех тестов, ответ к которым вам найти не удалось.

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

2
11 4 7
7 4 7

2
0 1
4 2
1
0 3

Задача C. Коммивояжёр возвращается! ≡

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

Как обычно, коммивояжёр хочет минимизировать транспортные расходы. Он выбирает начальную планету, прилетает туда на межгалактическом корабле, после чего посещает все остальные планеты системы в порядке, минимизирующем суммарную стоимость посещения, и на другом межгалактическом корабле улетает обратно. Естественно, коммивояжёр не хочет летать ни на какую планету дважды.

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

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

В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения a_ij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. a_ij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.

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

Выходной файл должен содержать единственное целое число — длину оптимального пути. Если не существует пути проходящего через все планеты, вывести -1.

Ограничения

1 ≤ n ≤ 19, a_ij ≤ 10⁸

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

3
-1 1 6
3 -1 7
4 9 -1

5

4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1

3

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

Условие

Дан набор a_i из N чисел. Необходимо расположить числа в последовательности a₁, a₂, …, a_N один за другим так, чтобы максимизировать следующую целевую функцию: (a₁*a₂ + a₂*a₃ + … + a_N−1*a_N)

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

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

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

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

Ограничения

2 ≤ N ≤ 16

1 ≤ a_i ≤ 10⁶

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

4
9 1 9 2

108

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

Условие

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

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100

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

2
..
.#

1

6
....X.
#XXX..

3

Задача Z. Профессор и песок ≡

Условие

Профессор одной из кафедр ДВФУ разработал инновационный метод для того, чтобы определять момента завершения лекции. У профессора есть двое песочных часов. В первых песок полностью пересыпается за a минут, во вторых — за b минут. В начале лекции весь песок в часах находится внизу и профессор переворачивает первые, вторые или сразу и те и другие часы. Как только песок в каких-нибудь часах полностью пересыпался, профессор может опять перевернуть первые, вторые или сразу и те и другие часы.

К концу лекции весь песок в часах вновь должен оказаться внизу. Лекция длится T минут.

По заданным a, b и T определите искомую последовательность переворотов.

Считается, что профессор переворачивает часы мгновенно.

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит количество тестов n. Далее следует n строк с целыми числами T, a, b.

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

Выходной файл должен содержать n блоков с ответами на тесты.

Первая строка каждого блока должна содержать количество действий, k. Далее должно следовать k строк с парами целых чисел t_i m_i в каждой, где t_i — время выполнения действия, m_i — одно из чисел 1, 2 или 3, обозначающее, что необходимо перевернуть первые, вторые или и те и другие часы соответственно. Для первого действия должно быть t_i = 0, для остальных t_i должно быть таким, что в этот момент песок хотя бы в одних часах только что полностью пересыпался вниз. Все t_i должны быть различны и расположены по возрастанию.

Для каждого теста выведите такой ответ, в котором количество действий не превосходит 500. Гарантируется, что в каждом тесте такой ответ существует.

Примечание: Поскольку блоки в выходном файле находятся один за другим, то, если указать неверное k в начале блока, все последующие блоки будут восприняты как ошибочные. Поэтому в случае частичного решения задачи рекомендуется указывать k = 0 для тех тестов, ответ к которым вам найти не удалось.

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

2
11 4 7
7 4 7

2
0 1
4 2
1
0 3