Плюсануть
Поделиться
Класснуть
Запинить

Задачи из рубрикатора

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

Условие задачи  
ID 33133: Камни
Камни
Темы: Динамическое программирование: один параметр    Простые игры   

На столе лежат N камней. За ход игрок может взять:
- 1 или 2 камня, если N делится на 3;
- 1 или 3, если N при делении на 3 дает остаток один;
- 1, 2 или 3, если N при делении на 3 дает остаток два.
Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.
 
Входные данные: вводится целое число \(0 < N <= 100\).
 
Выходные данные: выведите 1 или 2 – номер игрока, который выиграет при правильной игре.
 
Примеры
Входные данные Выходные данные
1 1 1
2 3 2

 

ID 27069: Кузнечик собирает монеты
Кузнечик собирает монеты
Темы: Динамическое программирование: один параметр   

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

 
Примеры
Входные данные Выходные данные
1
5 3
2 -3 5
7
3
1 2 4 5

ID 23408: Гвоздики
Гвоздики
Темы: Динамическое программирование: один параметр   

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить какие-то пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.
 
Входные данные: 
- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).
 
Выходные данные: выведите единственное число - минимальную суммарную длину всех ниточек.
 
 
Примеры
Входные данные Выходные данные
1
5
4 10 0 12 2
6

ID 23411: Ход конем
Ход конем
Темы: Динамическое программирование: один параметр   

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.
 
Клавиатура телефона выглядит так:
7 8 9
4 5 6
1 2 3
  0  
 
Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.
 
Входные данные: на вход подается целое число N (\(1<=N<=50\)).
 
Выходные данные: выведите файл искомое количество телефонных номеров.
 

Примеры
Входные данные Выходные данные
1 2 16

ID 23414: Покупка билетов
Покупка билетов
Темы: Динамическое программирование: один параметр   

За билетами на премьеру нового мюзикла выстроилась очередь из N человек, каждый из которых хочет купить 1 билет. На всю очередь работала только одна касса, поэтому продажа билетов шла очень медленно, приводя "постояльцев" очереди в отчаяние. Самые сообразительные быстро заметили, что, как правило, несколько билетов в одни руки кассир продаёт быстрее, чем когда эти же билеты продаются по одному. 
Поэтому они предложили нескольким подряд стоящим людям отдавать деньги первому из них, чтобы он купил билеты на всех. 
 
Однако для борьбы со спекулянтами кассир продавала не более 3-х билетов в одни руки, поэтому договориться таким образом между собой могли лишь 2 или 3 подряд стоящих человека.
 
Известно, что на продажу i-му человеку из очереди одного билета кассир тратит Ai секунд, на продажу двух билетов - Bi секунд, трех билетов - Ci секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.
 
Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).
 
Входные данные: 
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел Ai, Bi, Ci. Каждое из этих чисел не превышает 3600. Люди в очереди нумеруются начиная от кассы.
 
Выходные данные: выведите одно число - минимальное время в секундах, за которое могли быть обслужены все покупатели.
 
 
Примеры
Входные данные Выходные данные
1
5
5 10 15
2 10 15
5 5 5
20 20 1
20 1 1
12
2
2
3 4 5
1 1 1
4

ID 27081: Кузнечик-KMax
Кузнечик-KMax
Темы: Динамическое программирование: один параметр   

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N. Учитывайте, что Кузнечик не может прыгать назад.
 
Поскольку количество способов, которое нужно найти, может быть очень велико, вычислите его по модулю \(10^6 + 7\) , то есть найдите остаток от деления этого числа на \(10^6 + 7\) .
 
Входные данные: входная строка содержит натуральные числа N и K, разделённые пробелом. Гарантируется, что \(1 <= N ,\ K <= 10000\).
 
Выходные данные: программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N , вычисленное по модулю \(10^6+7\).
 
Примеры
Входные данные Выходные данные
1 10 5 236
2 100 50 934384