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

104 задачи
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Укладка плитки#21902
В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 109 + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 109 + 7.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток (1 ≤ n ≤ 100 000, 0 ≤ k < 2n). Последующие k строк содержат по два целых числа xi и yi , которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 109 + 7.
Ввод Вывод
2 0 7
3 0 22
3 1
2 1		 8


Динамическое программирование по профилюДинамическое программирование: один параметр
✓ 3✗ 11 200средняяВойти и решать
MTN DEW#21780
Чтобы подготовиться к предстоящей битве Bonkisilver должен прокачать свой скил, а, как известно, лучшим способом это сделать, является употребление mtn dew при прослушивании дабстепа в 4:20 по МСК. Полученный скилл вычисляется по формуле:

f(n) = f(n - 1) + f(n - 2) + f(n / 2),
где n - количество литров mtn dew, выражаемое целым числом. Операция n/2 означает целочисленное деление числа n на 2.

Также, известно, что

f(1) = 1 microCoinZ 
f(x) = 0 microCoinZ, при x < 1.

Помогите Bonkisilver сосчитать полученное количество microCoinZ.
 
Входные данные
На вход подается число n (0 <= n <= 70).
 
Выходные данные
Выведите одно число - полученный скилл. 
 
Примеры
№ Входные данные Выходные данные
1 1 1

PS: Mountain Dew, также MTN DEW — безалкогольный сильногазированный прохладительный напиток, торговая марка американской компании PepsiCo. 
Динамическое программированиеДинамическое программирование: один параметрРекуррентные последовательности
✓ 296✗ 741500лёгкаяВойти и решать
MLG pro#21779
Bonkisilver очень хочет стать MLG pro и попасть в FaZe clan. Для этого он каждый день практикуется в стрельбе из снайперской винтовки. В качестве поощрения, за каждый noscope он получает 2 пачки doritos, а за каждый quickscope - одну. Сколько вариантов сделать выстрелы было у Bonkisilver, если в итоге у него была n-1 пачка.
 
Входные данные
На вход подается число n (1 <= n <= 50).
 
Выходные данные
Выведите одно число - количество вариантов сделать выстрелы. 
 
 
Примеры
№ Входные данные Выходные данные
1 3 2
 
Динамическое программированиеДинамическое программирование: один параметр
✓ 113✗ 304700средняяВойти и решать
Задача Иосифа Флавия#18727
Задача Иосифа Флавия
 
Существует легенда, что Иосиф Флавий - известный историк первого века - выжил и стал известным благодаря математической одаренности. 
В ходе иудейской войны он в составе отряда из 41 иудейского воина был загнан римлянами в пещеру. Предпочитая самоубийство плену, воины решили 
выстроиться в круг и последовательно убивать каждого третьего из живых до тех пор, пока не останется ни одного человека. 
Однако Иосиф наряду с одним из своих единомышленников счел подобный конец бессмысленным - он быстро вычислил спасительные места 
в порочном круге, на которые поставил себя и своего товарища. И лишь поэтому мы знаем его историю.
 
В нашем варианте мы начнем с того, что выстроим в круг N человек, пронумерованных числами от 1 до N, и будем исключать каждого k-ого до тех пор, пока не уцелеет только 
один человек. (Например, если N=10, k=3, то сначала умрет 3-й, потом 6-й, затем 9-й, затем 2-й, затем 7-й, потом 1-й, потом 8-й, за ним - 5-й, и потом 10-й. Таким образом, уцелеет 4-й.)
 
Задача: определить номер уцелевшего.
 
Входные данные: числа N и k вводятся из строки. 
Ограничения: 1<=N<=500, 1<=k<=100.
 
Выходные данные: Программа должна выдавать номер уцелевшего человека.
 
Пример входного файла:
10 3
 
Пример выходного файла:
4
Динамическое программирование: один параметр
✓ 93✗ 192700средняяВойти и решать
Поделиться
Класснуть