#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

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

#1150

Таблица

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2008 (четвертый интернет-этап), запад, Задача A ]

Рассмотрим прямоугольную таблицу размером n  m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.

Обозначим через a_ij число, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a₁₁, a₁₂, …, a₁_m. Затем заполняются строки с номерами от 2 до n. Число a_ijвычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом a_ij. Все вычисления при этом выполняются по модулю r.





				a_i,j

Более точно, значение a_ij вычисляется по следующей формуле:

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

2	3	4	5
5 = 2 + 3	9 = 2 + 3 + 4	12 = 3 + 4 + 5	9 = 4 + 5
23 = 2 + 3 + 4 + 5 + 9	0 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 40	4 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 40	33 = 3 + 4 + 5 + 12 + 9

Требуется написать программу, которая по заданной первой строке таблицы (a₁₁, a₁₂, …, a₁_m), вычисляет последнюю строку, как описано выше.

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

Первая строка входного файла содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 10⁹) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a₁₁, a₁₂, …, a_{1m. Все a_1i}неотрицательны и не превосходят 10⁹.

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

В первой строке выходного файла необходимо вывести m чисел – последнюю строку таблицы: a_n₁, a_n₂, …, a_nm_.

Примеры

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

2 3 10
1 2 3

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

3 6 5

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

3 3 10
1 1 1

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

8 0 8

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

3 4 40
2 3 4 5

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

23 0 4 33

#1211

Числа

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача C ]

Задана последовательность чисел. Требуется подсчитать количество вариантов разбиения этой последовательности на неотрицательные числа, не превосходящие заданного числа.

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

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

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

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

Первая строка входного файла содержит три целых числа — n, C и k (1 ≤ n ≤ 50000, 1 ≤ C ≤ 10⁸, 1 ≤ k ≤ 18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

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

В выходной файл выведите последние k цифр искомого количества последовательностей (без ведущих нулей).

Разбалловка для личной олимпиады

Тесты 1-8 — \(n \le 7\) Оценивается в 30 баллов.

Тесты 9-53 — дополнительных ограничений нет. Группа тестов оценивается в 70 баллов.

Примеры

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

3 11 2
111

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

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

19 9 1
0123456789876543210

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

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

1 8 3
9

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

#1225

Склад

Темы: [Пересечение множеств] [Задача о рюкзаке]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2007, Задача E ]

На роботизированном складе имеется N отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость c_i. Груз с номером i имеет размер s_i, поступает на склад в момент времени a_i и забирается со склада в момент времени d_i.

Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Свободное место в пустом отсеке совпадает с его вместимостью. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.

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

Если отсеков с достаточным количеством свободного места нет, робот пытается переместить грузы, уже расположенные в отсеках. Для этого он пытается найти такой отсек и такой груз в нем, что перемещение его в другой отсек обеспечивает достаточное количество свободного места для размещения поступившего груза. Если таких вариантов перемещения грузов несколько, то выбирается тот вариант, в котором потребуется перемещение груза с минимальным размером. Если и таких вариантов несколько, то выбирается тот вариант перемещения, при котором в отсеке, из которого перемещается груз, после перемещения свободное место будет минимально, а при прочих равных — тот, при котором в отсеке, в который осуществляется перемещение, свободное место после перемещения будет минимально. Если и после этого остается более одного варианта, то выбирается тот вариант, при котором номер перемещаемого груза минимален, и номер отсека, в который он перемещается, – также минимален. Если варианта с перемещением одного груза найти не удалось, то груз не принимается на склад.

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

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

Первая строка содержит два целых числа: N — количество отсеков, и M — количество грузов (1 ≤ N ≤ 10, 1 ≤ M ≤100). Вторая строка содержит N целых чисел c_i, определяющих вместимости отсеков (1 ≤ c_i ≤ 10⁹). Последующие M строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером s_i, временем поступления на склад a_i и временем, когда его забирают со склада d_i (1 ≤ s_i ≤ 10⁹, 1 ≤ a_i < d_i ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.

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

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

Возможны следующие сообщения:

put cargo X to cell Y — положить груз с номером X в отсек с номером Y;

move cargo X from cell Y to cell Z — переложить груз с номером X из отсека с номером Y в отсек с номером Z;

take cargo X from cell Y — достать груз с номером X из отсека с номером Y.

cargo X cannot be stored — если груз с номером X разместить невозможно.

Примеры

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

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

put cargo 1 to cell 1
take cargo 1 from cell 1
cargo 2 cannot be stored

#1226

Игра с шашками

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Московская областная олимпиада, 2007, Задача F ]

Поле для игры с шашками – длинная горизонтальная полоска, размеченная на клетки. Клетки пронумерованы от 1 до N (2 < N < 10000). На поле стоят две шашки. Позиция каждой из шашек определяется номером клетки, в которой она стоит.

Играют двое. Каждый игрок при своем ходе должен переместить любую шашку на одну, две или три клетки в сторону клетки 1 (сделать 1, 2 или 3 шага). Перепрыгивать через стоящую впереди шашку нельзя, но можно сдваивать шашки. На сдваивание шашек тратится два шага из трех доступных игроку (то есть сдваивать можно либо шашки, стоящие вплотную друг к другу, либо шашки, между которыми есть только одна пустая клетка). Если произошло сдваивание – ход передается другому игроку, который делает ход одной шашкой , оставив другую на месте.

Выигрывает тот, кто сдвоит шашку на клетке с номером 1.

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

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

В первой строке содержится число K (0 < K < 10) – количество начальных позиций. В последующих K строках содержится по два целых числа от 3 до 10000, разделенных пробелом – номера начальных позиций шашек на игровом поле.

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

Выводится K строчек – ответ на каждую начальную позицию.

Если при заданной начальной позиции шашек в игре не достигается выигрыш (при правильной игре противника) выводится слово NO.

Если выигрыш достижим, то выводится первый ход начинающего игру, который приводит к его выигрышу независимо от того, как играет соперник. Ход описывается парой чисел i, j через пробел, означающих, что выигрышный ход игрока – это перемещение шашки из клетки с номером i в клетку с номером j. Например, «4 3» означает, что игрок двигает шашку, стоящую в клетке 4, на одну клетку в сторону клетки 1.

Примечание

Ответ на тест из примера:
NO
11 10
12 11
NO
15 12
12 10

Примеры

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

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

YES
NO