Динамическое программирование

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

 

Входные данные 
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).  

 

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

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).

 

 

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

 

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).  

 

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

На столе лежат N камней. За ход игрок может взять:

- 1 или 2 камня, если N делится на 3;

- 1 или 3, если N при делении на 3 дает остаток один;

- 1, 2 или 3, если N при делении на 3 дает остаток два.

Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.

 

Входные данные: вводится целое число \(0 < N <= 100\).

 

Выходные данные: выведите 1 или 2 – номер игрока, который выиграет при правильной игре.

Дан набор гирь массой m­1, …, mN. Можно ли их разложить на две чаши весов, чтобы они оказались в равновесии?

 

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

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

 

Выходные данные: выведите YES или NO.

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

 

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

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

 

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

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

 

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

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

 

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

Дано N предметов массой m1, …, mN и стоимостью c1, …, cN соответственно. 

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

 

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

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

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

 

Выходные данные: выведите номера предметов (числа от 1 до N), которые войдут в рюкзак наибольшей стоимости (по одному номеру в строке).

Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?

 

В единственной строке записано одно натуральное число - количество деревьев N (1 ≤ N ≤ 50).

 

В единственную строку нужно вывести одно число - количество способов покраски.
 

Ввод	Вывод
3	12

На вход программы подается натуральное число N, а затем N целых чисел. Необходимо определить максимальную сумму смежных элементов последовательности. N не превышает 1000000, каждый элемент последовательности не превосходит по модулю 100.

Пояснения: для заданной последовательности чисел (-2 1 -3 4 -1 2 1 -5 4) наибольшую сумму можно получить для смежной последовательности элементов: 4 -1 2 1.

Решение на 2 балла начисляются при прохождении программой 50% тестов, 3 балла - при прохождении программой 75% тестов.

 

Одной из наиболее распространенных опечаток при наборе текста является перестановка двух соседних символов, например, вместо слова «программа» набрано слово «прогармма». Расстояние Левенштейна не учитывает такие опечатки: при вычислении расстояния Левенштейна одна перестановка будет считаться за два редактирования (например, удаление и вставка символа).

 

При вычислении расстояния Дамерау-Левенштейна, помимо операций замены, вставки и удаления символа допускается еще операция перестановки двух соседних символов. При этом между переставленными символами нельзя вставлять другие символы.

 

Определите расстояние Дамерау-Левенштейна для двух данных строк.

Входные данные
Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.
 
Выходные данные
Требуется вывести одно число – расстояние Дамерау-Левенштейна для данных строк.
 

Примеры

№	Входные данные	Выходные данные
1	XABCDE ACBYDF	4

Дана текстовая строка. С ней можно выполнять следующие операции:

 

Например, при помощи первой операции из строки "СОК" можно получить строку "СУК", при помощи второй операции - строку "ОК", при помощи третьей операции - строку "СТОК.

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

 

Определите расстояние Левенштейна для двух данных строк.

 

Программа получает на вход две строки, длина каждой из которых не превосходит 1000 символов, строки состоят только из заглавных латинских букв.

 

Требуется вывести одно число – расстояние Левенштейна для данных строк.
 
 

Примеры

№	Входные данные	Выходные данные
1	ABCDEFGH ACDEXGIH	3

 

Даны две последовательности, требуется найти и вывести их наибольшую общую подпоследовательность.

 

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

 

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

 

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

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 3  2 3 1	2 3

Даны две последовательности, требуется найти длину их наибольшей общей подпоследовательности.

 

В первой строке входных данных содержится число N – длина первой последовательности (1 ≤ N ≤ 1000). Во второй строке заданы члены первой последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

 

В третьей строке записано число M – длина второй последовательности (1 ≤ M ≤ 1000). В четвертой строке задаются члены второй последовательности (через пробел) – целые числа, не превосходящие 10000 по модулю.

 

Требуется вывести одно число – длину  наибольшей общей подпоследовательности двух данных последовательностей или 0, если такой подпоследовательности нет.
 
 

Примеры

№	Входные данные	Выходные данные
1	3 1 2 3 3  2 3 1	2

Черепаха хочет переползти из левого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 16 ) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Определите, сколькими различными способами Черепаха может добраться до цели.

 

Входная строка содержит два натуральных числа: размеры поля N и M , разделённые пробелом ( 1 ≤ N , M ≤ 16 ).

 

Программа должна вывести одно число: количество различных маршрутов из левого верхнего угла поля в правый нижний.
 
 

Примеры

№	Входные данные	Выходные данные
1	3 3	6

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

 

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

Входная строка содержит одно натуральное число – количество клеток в ряду N .

 

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

Программа должна вывести количество безопасных способов расстановки N клеток в ряд.

Ввод	Вывод
5	13

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.

 

Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите его по модулю \(10^6 + 7\) , то есть найдите остаток от деления этого числа на \(10^6 + 7\) .

 

Входные данные: входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что \(1 <= N ,\ K <= 10000\).

 

Выходные данные: программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N , вычисленное по модулю \(10^6+7\).

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

 

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 .

 

Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N .
 

Ввод	Вывод
5 4	8

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

 

Входная строка содержит натуральное число N ( 1 ≤ N ≤ 45 ).

 

Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N .
 

Ввод	Вывод
3	2
10	55

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.

 

На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.

 

Входные данные
- в первой строке вводятся два натуральных числа: N и K (\(2 <= N ,\ K <= 10000\)), разделённые пробелом;
- во второй строке записаны через пробел N-2 целых числа – количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N-1-го. Если это число отрицательное, Кузнечик теряет монеты.
Гарантируется, что все числа по модулю не превосходят 10000.

 

- в первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик;
- во второй строке выводится число прыжков Кузнечика;
- в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).

 

Если правильных ответов несколько, выведите любой из них.

Даны N целых чисел X1, X2, ..., XN. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

 

В первой строке находится число N. В следующей строке - N чисел через пробел. 1 <= N <= 10 000, 1 <= Xi <= 60 000.

 

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

Примеры

№	Входные данные	Выходные данные
1	5 1 3 5 2 4	3 1 3 4