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

Это Бомба#24906

Мише приснился страшный сон как будто ему очень быстро необходимо разминировать бомбу! На большом дисплее бомбы он видит одно число, рядом есть клавиатура с цифрами (явно для экстренной отмены взрыва), а где-то внизу уже идёт обратный отсчёт. По удачному стечению обстоятельств у него с собой есть инструкция для разминирования, в которой ему нужно срочно разобраться. В такой тяжялой ситуации мозги у Миши совсем отказали и ему явно нужна помощь.

Инструкция:

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

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

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

✓ 25✗ 16500лёгкаяВойти и решать

Максимальная прибыль#24755

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

Про каждую задачу известно время t_i, которое нужно затратить, чтобы сделать её, а также прибыль p_i, которую сделанная задача принесёт компании. Вы хотите включить в план некоторые задачи так, чтобы:

Суммарное время, затраченное на выполнение задач, включённых в план, не превышало T.
Суммарная прибыль от выполнения этих задач была максимальна.

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

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

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

В первой строке находятся натуральные числа T (1 ≤ T ≤ 100 000) и n (1 ≤ n ≤ 10) - число единиц времени в месяце и число задач.

Следующие n строк содержат по два натуральных числа t_i и p_i (1 <= t_i, p_i <= 100 000) - время, которое необходимо затратить на выполнение i-й задачи и прибыль, которую можно получить, выполнив её.

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

Выведите единственное число — максимальная прибыль, которую можно получить, составив план, удовлетворяющий написанным выше условиям.

Примеры

№	Входные данные	Выходные данные
1	10 3 8 100 3 10 3 10	100
2	10 4 5 10 5 20 2 5 2 6	31

битмаски Задача о рюкзаке

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

Покупка билетов#23414

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

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

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

Известно, что на продажу i-му человеку из очереди одного билета кассир тратит A_i секунд, на продажу двух билетов - B_i секунд, трех билетов - C_i секунд. Напишите программу, которая подсчитает минимальное время, за которое могли быть обслужены все покупатели.

Обратите внимание, что билеты на группу объединившихся людей всегда покупает первый из них. Также никто в целях ускорения не покупает лишних билетов (то есть билетов, которые никому не нужны).

Входные данные:
- в первой строке записано число N - количество покупателей в очереди (\(1<=N<=5000\));
- далее идет N троек натуральных чисел A_i, B_i, C_i. Каждое из этих чисел не превышает 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

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

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

Ход конем#23411

Шахматная ассоциация решила оснастить всех своих сотрудников такими телефонными номерами, которые бы набирались на кнопочном телефоне ходом коня. Например, ходом коня набирается телефон 340-4927. При этом телефонный номер не может начинаться ни с цифры 0, ни с цифры 8.

Клавиатура телефона выглядит так:

7	8	9
4	5	6
1	2	3
	0

Напишите программу, определяющую количество телефонных номеров длины N, набираемых ходом коня.

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

Выходные данные: выведите файл искомое количество телефонных номеров.

Примеры

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

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

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

Подпоследовательности#23409

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

подпоследовательности.

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

В первой строке входного файла записано число N - длина последовательности (1 <= N <= 1000). Во второй строке записана сама последовательность (через пробел). Числа последовательности - целые числа, не превосходящие 10000 по модулю.

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

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

Примеры

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

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

✓ 509✗ 950300лёгкаяВойти и решать

Гвоздики#23408

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

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

- в первой строке записано число N - количество гвоздиков (\(2 <= N <= 100\));
- в следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Выходные данные: выведите единственное число - минимальную суммарную длину всех ниточек.

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

✓ 650✗ 1 357600лёгкаяВойти и решать

Минимальный путь в таблице#23407

В прямоугольной таблице NxM (в каждой клетке которой записано некоторое число) в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено).

При проходе через клетку с игрока берут столько у.е., какое число записано в этой клетке (деньги берут также за первую и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может попасть в правый нижний угол.

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

В первой строке записаны два числа N и M - размеры таблицы (\(1<=N<=20\), \(1<=M<=20\)). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

Выходные данные
Выведите минимальную сумму, потратив которую можно попасть в правый нижний угол.

Примеры

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

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

✓ 722✗ 745400лёгкаяВойти и решать

Минимальный путь в таблице#22016

В прямоугольной таблице NxM (в каждой клетке которой записано

некоторое число) в начале игрок находится в левой верхней клетке.

За один ход ему разрешается перемещаться в соседнюю клетку

либо вправо, либо вниз (влево и вверх перемещаться запрещено).

При проходе через клетку с игрока берут столько у.е., какое число

записано в этой клетке (деньги берут также за первую

и последнюю клетки его пути).

Требуется найти минимальную сумму у.е., заплатив которую игрок может

попасть в правый нижний угол.

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

Во входном файле задано два числа N и M - размеры таблицы (1<=N<=20,

1<=M<=20). Затем идет N строк по M чисел в каждой - размеры штрафов

в у.е. за прохождение через соответствующие клетки (числа от 0 до 100).

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

В выходной файл запишите минимальную сумму, потратив которую можно попасть

в правый нижний угол.

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

3 4

1 1 1 1

5 2 2 100

9 4 2 1

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

Динамическое программирование на таблицах

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

Dank numbers#21778

Число является dank number, если все его цифры идут в неубывающем порядке. Чтобы получить dank kush, Bonkisilver должен назвать все n-значные dank numbers. Вас не просят узнать все такие числа, Вам лишь нужно вывести их количество.

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

На вход подается число n (0 <= n <= 50).

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

Выведите одно число - количество n-значных dank number.

Примеры

№	Входные данные	Выходные данные
1	9	24310

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

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

Треугольник Паскаля#18786

Треугольник Паскаля строится следующим образом. Первая строка состоит из одного числа, равного единице. Каждая следующая

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

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

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

Примечание
Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint.

Примеры

№	Входные данные	Выходные данные
1	8	1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1

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

✓ 611✗ 650400лёгкаяВойти и решать

Задача Иосифа Флавия#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средняяВойти и решать