#1106

SMS

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

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2007, Задача J ]

SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй – то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке.

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

Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.

Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.

К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.

Вы получили SMS-сообщение, набранное на этом телефоне. Известно, что изначально оно состояло из N символов. Напишите программу, которая определит количество вариантов исходных сообщений, которые при вводе могли превратиться в то, что вы получили (если вариантов окажется 0, то это будет означать, что у телефона сломалось что-то еще).

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

Сначала записана длина исходного сообщения N (1≤N≤80). Вторая строка содержит полученное SMS-сообщение – последовательность не более чем из 80 заглавных латинских букв.

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

Выведите одно число – количество вариантов исходного сообщения.

Примеры

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

4
MAMA

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

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

2
WWW

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

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

10
MAMA

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

#1118

0-1 Рюкзак

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

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второе строке вводятся N натуральных чисел m_i, не превышающих 100.

Во третьей строке вводятся N натуральных чисел с_i, не превышающих 100.

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

Выведите наибольшую стоимость рюкзака.

Примеры

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

1 597
18
16

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

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

2 27
30 35
3 9

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

#1119

0-1 рюкзак: наибольший вес

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

Дано N золотых слитков массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую массу золота можно унести в таком рюкзаке?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел m_i, не превышающих 100.

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

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

Примеры

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

2 3195
38 41

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

#1120

0-1 рюкзак: точный вес

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

Дано N золотых слитков массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Можно ли набрать вес в точности M?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второй строке вводятся N натуральных чисел m_i, не превышающих 100.

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

Выведите YES или NO.

Примеры

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

1 5968
18

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

NO

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

4 102
50 52 54 2

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

YES

#1121

0-1 рюкзак: минимум предметов

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

Дано N предметов массой m₁, …, m_N. Ими наполняют рюкзак, который выдерживает вес не более M. Как набрать вес в точности M, используя как можно меньше предметов?

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

В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000.

Во второе строке вводятся N натуральных чисел m_i, не превышающих 100.

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

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

Примеры

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

1 5968
18

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