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

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

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

Условие задачи  
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 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

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

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

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 23411: Ход конем
Ход конем
Темы: Динамическое программирование: один параметр   

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

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

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 37889: Слинки "Радуга"
Слинки "Радуга"
Темы: Динамическое программирование: один параметр   

Слинки — игрушка-пружина, созданная в 1943 году в США Ричардом Джеймсом. В нашей стране она называлась просто Радуга. Все дети любили ее запускать со ступенек, считая у кого она спустится ниже.
Обычно "Радуга" в руках детей спускалась на следующую ступеньку, на ступеньку через одну или через 2. (Например, если Радугу запускали с 10-ой ступеньки, то она могла остановиться на 9-ой, 8-ой или 7-ой.)
Допустим на лестнице N ступенек. Определите число всевозможных "маршрутов" Радуги с вершины лестницы на землю.


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

Вводится одно число \(0 < N < 31\).


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

Выведите одно число — количество "маршрутов" Радуги.

 

 

Примеры
Входные данные Выходные данные
1 4 7

 

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

Заботливые хозяева квартиры заботятся о таракане Василии. Вечером они выкладывают для него в ряд N хлебных крошек, которые он очень любит. Переходя от одной хлебной крошки к другой, таракан Василий может съесть ее, а может и не съесть. Но он никогда не ест две хлебные крошки подряд.
Посчитайте сколько различных вариантов полакомиться хлебными крошками есть у таракана Василия.

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

На вход программы поступает целое число N  (\(1<=N<=100\) ).


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

Выведите ответ на задачу.

 

 

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

 

ID 37891: Играем в Камушки
Играем в Камушки
Темы: Динамическое программирование: один параметр   

Когда-то в далеком детстве мы все с удовольствием играли в игру "Камушки" или "Пять камешков", кто как называл. Для игры нужны были обычные камешки, которые можно было запросто найти на улице. Играть можно было в любом месте, Для игры нужна была небольшая ровная площадка утоптанной земли или ровный пол крыльца или беседки. 
Первый шаг игры заключался в следующем. На землю перед собой бросаются все пять камешков. Выбирался один из них. Это биток. Этот камешек подбрасывается в воздух и, пока он летит, необходимо поднять один из оставшихся на земле камешков и успеть подхватить этой же рукой летящий. Подобранный камешек откладывается в сторону и действие повторяется для всех оставшихся камешков.
На следующих шагах количество камешков, которые надо подхватить увеличивается. Последним шагом был экзамен, когда необходимо было подбросить все собранные камешки в воздух и поймать их тыльной стороной ладони, а затем опять подбросить, и поймать открытой ладонью. Сколько камешков в итоге оставалось, столько баллов и получаешь. Ход переходит к следующему игроку, который также повторяет все шаги. Далее запускался новый тур игры. Выигрывал тот, кто набирал больше всего баллов за все туры.
Многие ребята усложняли игру самыми разными способами.
Допустим у ребят есть бесконечное число камешков лежащих на земле. В конце тура им необходимо поймать в ладони не все камешки, а ровно столько, чтобы общее число баллов у них увеличилось на 1 или удвоилось или утроилось. Перед началом игры у всех уже имеется 1 балл. Победителем будет считаться тот, кто быстрее наберет N баллов.
Будем считать, что у всех играющих достаточно опыта игры, и они всегда доходят до экзамена с нужным им числом камней (чтобы была возможность нужное число баллов увеличить на 1, удвоить или утроить).

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

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

Программа получает на вход одно число, не превосходящее 106.


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

Требуется вывести одно число: наименьшее количество искомых операций.

 

 

Примеры
Входные данные Выходные данные
1 1 0
2 5 3
3 32718 17