#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

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

#654

SMS

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

Сообщения SMS сотового телефона MOBILA составлены из прописных латинских букв. Если буква первая на кнопке, нужно нажать эту кнопку один раз, чтобы добавить букву в сообщение. Если буква вторая - нужно нажать кнопку дважды и т.д. Так, чтобы набрать слово "SMS", нужно нажать

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

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

(ABC)(пауза)(ABC)

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

(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)

соответствует сообщению "CAA". К сожалению, сотовые телефоны этой модели давно не производятся, и остался только один такой телефон. Он может произвольно вставлять и игнорировать паузы во время ввода сообщения, что может привести к некоторым изменениям в сообщениях. Например, введя MOSCOWQUARTERFINAL, можно получить вместо этого OMSCMNWQTTARTERPDEINAL. Вы получили SMS-сообщение и знаете, что оригинальное сообщение содержало N букв. Чтобы определить вероятность угадывания оригинального сообщения, найдите число возможных сообщений, которые могли превратиться в то, которое Вы получили.

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

В первой строке задана длина оригинального сообщения \(N\). Вторая строка содержит полученное SMS-сообщение. 1 <= \(N\) <= 80, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от 1 до 80 букв.

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

Вывести число сообщений из \(N\) букв, которые, будучи набранными на на этом телефоне, могут превратиться в данное сообщение.

Примеры

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

8
ADGJMPTW

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

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

9
ADGJMPTW

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