Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Выборы#21952

Скоро в Соединенных Штатах Берляндии пройдут выборы президента. На эту ответственную должность претендуют два кандидата: Дядя Сэм и Дядя Фродо. Вы работаете аналитиком в пред- выборном штабе Дяди Сэма, и вам поручено помочь ему победить конкурента. Раздуть газетный скандал из одержимости оппонента бросанием колец в жерла вулканов не получилось, так что при- дётся воспользоваться математикой.

Казалось бы, чтобы выиграть, необходимо убедить проголосовать за нашего кандидата более половины пришедших на выборы. Оказывается, что иногда нужно гораздо меньше! Для того чтобы понять, как это возможно, рассмотрим подробнее процедуру голосования.

Как вы знаете, Соединенные Штаты Берляндии разделены на несколько административных ре- гионов первого уровня — штатов. Сначала в каждом из штатов проходят местные выборы, по итогам которых каждый штат отдаёт свой голос за одного из кандидатов. Если не менее половины штатов выбрало Дядю Сэма, то выигрывает он (в случае равенства голосов Дядя Сэм имеет преимущество как действующий президент), иначе побеждает Дядя Фродо. Все штаты, в свою очередь, состоят из административных регионов второго уровня, каждый из которых представлен выборщиком из административных регионов третьего уровня и так далее. Последний уровень состоит из отдельных жителей Берляндии. Всего в Берляндии N жителей и K уровней административных единиц. Одним из ключевых принципов этой страны является равенство, так что любой регион i-го уровня делится на одинаковое число регионов следущего уровня (в том числе содержит одинаковое число граждан).

Так получилось, что делением на регионы поручили заняться именно вам, то есть в ваших руках назначить, на сколько именно административных единиц i-го уровня делится (i−1)-ая администра- тивная единица.

Также у вас есть сильный инструмент влияния на выбор людей — нефтяные бурли. Чтобы заста- вить одного избирателя отдать свой голос за Дядю Сэма, достаточно дать ему скромный подарок в размере одного нефтяного бурля.

К несчастью, изначально все N жителей Соединённых Штатов Берляндии собираются отдать свой голос за Дядю Фродо. Требуется определить минимальное количество нефтяных бурлей, ко- торое достаточно потратить для победы на выборах.

Формат входных данных

В единственной строке ввода находятся два целых числа N и K (1 <= N <= 10¹⁵ , 1 <= K <= 10).

Формат выходных данных
Требуется вывести единственное число — минимальное количество нефтяных бурлей, которое придётся потратить на предвыборные подарки при наилучшем разбиении на регионы.

Примеры

Ввод	Вывод
9 2	4
12 3	2

Замечание
Берляндские законы не запрещают, чтобы страна состояла из одного штата, а город — одного жителя. Аналогично с остальными типами регионов.

На рисунке 1 черным цветом отмечены те регионы, в которых победил Дядя Сэм. На нижнем уровне черными изображены вершины, соответствущие подкупленным конкретным жителям.

✓ 2✗ 771 200средняяВойти и решать

Укладка плитки#21902

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

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

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

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

Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹ + 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.

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

✓ 297✗ 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

Пример выходного файла:

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

✓ 93✗ 192700средняяВойти и решать