#625

Копилка

Темы: [Задача о рюкзаке]

Задан вес \(E\) пустой копилки и вес \(F\) копилки с монетами. В копилке могут находиться монеты \(N\) видов, для каждого вида известна ценность \(P_i\) и вес \(W_i\) одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.

Ограничения

\(1 \le E\le F\le 10000\), \(1 \le N \le 500\), \(1\le P_i\le 50000\), \(1\le W_i \le 10000\), все числа целые.

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

В первой строке находятся числа \(E\) и \(F\), во второй - число \(N\), в следующих \(N\) строках - по два числа, \(P_i\) и \(W_i\).

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

Выводятся два числа через пробел - минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, - вывести "This is impossible.".

Примеры

Ввод	Вывод
1000 1100 2 1 1 5 2	100 250
1000 1010 2 6 3 2 2	10 16
1000 2000 1 10 3	This is impossible.

#631

Гангстеры

Темы: [Динамическое программирование: два параметра]

\(N\) гангстеров собираются в ресторан. \(i\)-й гангстер приходит в момент времени \(T_i\) и имеет богатство \(P_i\). Дверь ресторана имеет \(K\) + 1 степень открытости, они обозначаются целыми числами из интервала [0, \(K\)]. Степень открытости двери может изменяться на единицу в единицу времени, то есть дверь может открыться на единицу, закрыться на единицу или остаться в том же состоянии. В начальный момент времени дверь закрыта (степень открытости 0). \(i\)-й гангстер заходит в ресторан, только если дверь открыта специально для него, то есть когда степень открытости двери соответствует его полноте \(S_i\). Если в момент, когда гангстер подходит к ресторану, степень открытости двери не соответствует его полноте, он уходит и больше не возвращается. Ресторан работает в интервале времени [0, \(T\)]. Требуется собрать гангстеров с максимальным суммарным богатством в ресторане, открывая и закрывая дверь соответствующим образом.

Входные данные

В первой строке находятся числа \(N\), \(K\), \(T\), во второй - \(T_1\), \(T_2\), ..., \(T_N\), в третьей - \(P_1\), \(P_2\), ..., \(P_N\). в четвёртой - \(S_1\), \(S_2\), ..., \(S_N\). Числа в строках разделены пробелами. 1 <= \(N\) <= 100, 1 <= \(K\) <= 100, 1 <= \(T\) <= 30 000, 0 <= \(T_i\) <= \(T\), 1 <= \(P_i\) <= 300, 1 <= \(S_i\) <= \(K\), все числа целые.

Выходные данные

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

Примеры

Входные данные

Выходные данные

#637

Маршрут(2)

Темы: [Динамическое программирование на таблицах]

Дана матрица \(N\)x\(N\), заполненная положительными числами. Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали, нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по пути длиной \(K\) (клетку можно посещать несколько раз).

Входные данные

В первой строке находятся разделенные пробелом числа \(N\) и \(K\). Затем идут \(N\) строк по \(N\) чисел в каждой. 2 <= \(N\) <= 100, элементы матрицы имеют значения от 1 до 9999, 1 <= \(K\) <= 2000, все числа целые.

Выходные данные

Вывести одно число - максимальную сумму.

Примеры

Входные данные

5 7
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 100

Выходные данные

#642

Суммы

Темы: [Динамическое программирование: два параметра]

Дано N целых чисел A₁, A₂, ..., A_N. Требуется найти количество различных значений сумм вида k₁A₁ + k₂A₂ + ... + k_NA_N.
Ограничения: 1 <= N <= 500, 0 <= A_i <= 100, 0 <= k_i <= 1, все числа целые.
Ввод: В первой строке находится число N, во второй - A₁, A₂, ..., A_N через пробел.
Вывод: Вывести одно число - количество различных значений сумм.
Примеры

Ввод 1    Ввод 2    Ввод 3
3         3         5
1 1 2     1 3 2     49 100 98 49 0
Вывод 1   Вывод 2   Вывод 3
5         7         10

Примеры

Входные данные

1
0

Выходные данные

#648

Сообщение

Темы: [Динамическое программирование: один параметр]

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Входные данные

В первой строке содержится последовательность цифр. Цифр не более 100.

Выходные данные

Вывести одно число.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные