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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

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

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

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

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 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

Задача C. Реформа галактических вооруженных сил ≡

Условие

Армия галактического альянса состоит из 2 N дивизионов боевых дроидов. Верховное командование приняло решение сократить количество дивизионов вдвое, объединив их попарно. Объединение двух дивизионов происходит следующим образом: каждый из дивизион разбивается на одинаковое количество K_i отрядов дроидов, после чего отряды сливаются и формируют K_i увеличенных отрядов, составляющих новый объединенный дивизион.

Программное обеспечение дроидов поддерживает разбиение дивизиона дроидов только на равные по количеству отряды. Например, дивизион из 6 дроидов может быть разбит на 1 отряд из 6 дроидов, 2 отряда из 3 дроидов, 3 отряда из 2 дроидов или 6 отрядов из 1 дроида.

Считается, что после объединения двух дивизионов, максимальную эффективность в бою имеет объединенный дивизион с наибольшим количеством отрядов. Например, максимально эффективный способ объединить два дивизиона, состоящие из из 6 и 4 дроидов — это разбить каждый на два отряда по 3 и 2 дроида, соответственно. Затем сформировать два увеличенных отряда по 5 дроидов. Новый объединенный дивизион будет состоять из 10 дроидов, состоящих в 2 отрядах.

Рассмотрим армию, состоящую из 4 дивизионов: 4 9 3 6. Возможные варианты разбиения дивизионов на равные по численности отряды: 1 дивизион: 1 по 4, 2 по 2, 4 по 1. 2 дивизион: 1 по 9, 3 по 3, 9 по 1. 3 дивизион: 1 по 3, 3 по 1. 4 дивизион: 1 по 6, 2 по 3, 6 по 1.

Соответственно, оптимальным решением будет объединение дивизионом 1 и 4 с разбиением на 2 отряда каждого, а также дивизионов 2 и 3 с разбиением на 3 отряда каждого. Общее количество отрядов в армии после объединения — 5.

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

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

Входной файл содержит целое положительно число N, за которым следуют 2 N целых положительных чисел D_i — количество дроидов в i-ом дивизионе.

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

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

Ограничения

1 ≤ N ≤ 10; 1 ≤ D_i ≤ 10⁹

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

2
1 2 3 4

3

2
4 9 3 6

5

2
30 18 5 12

11

Задача 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

Задача E. Доклад с картинками ≡

Условие

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

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

Зная высоту каждой картинки в сантиметрах h_i, определите порядок следования картинок, при котором полученный документ будет иметь наибольшее количество страниц.

В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.

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

Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h₁… h_n.

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

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

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 10⁸;

1 ≤ h_i ≤ k;

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

4 10
4 6 4 6

4 4 6 6

Задача F. Чудик в Цветландии ≡

Условие

Однажды Чудик попал в загадочную страну Цветландию. Эта страна имеет форму квадрата, разделённого на N × N маленьких квадратиков — регионов.

В каждом регионе растут цветы определённого сорта. У цветов каждого сорта есть определённый период цветения T. Цветы растут T дней, после чего увядают и начинают расти заново.

Цветы каждого региона в каждый из дней имеют определённую силу запаха, В первый день роста цветы не пахнут (сила запаха равна нулю), затем сила запаха увеличивается на единицу каждый день, вплоть до дня увядания. Таким образом, цветы с периодом цветения T в k-й день имеют силу запаха (k−1) mod T.

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

Чудик выбирает, с какого региона он начнёт путешествие, и отправляется в путь. Путешествие Чудика длится K дней. За один день Чудик должен переместиться в соседний (сверху, справа, снизу или слева) регион.

В k-й день путешествия Чудика в регионе с координатами (x, y) цветы имеют силу запаха (k−1) mod T(x, y), где T(x, y) — период цветения цветов этого региона.

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

Комментарий к примеру

Силы запаха в регионах по дням:

0 0
0 0

1 1
1 1

0 0
2 0

1 1
0 1

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

Входной файл содержит целые числа N K. Далее следуют N² целых чисел T(x, y).

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

Выходной файл должен содержать целое число — максимальную сумму сил запаха.

Ограничения

2 ≤ N ≤ 100

1 ≤ K ≤ 100

2 ≤ T(x, y) ≤ 100

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

2 4
2 2
3 2

4