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

Черепаха#27086

Черепаха хочет переползти из левого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 16 ) в правый нижний. За один шаг она может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Определите, сколькими различными способами Черепаха может добраться до цели.

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

Входная строка содержит два натуральных числа: размеры поля N и M , разделённые пробелом ( 1 ≤ N , M ≤ 16 ).

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

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

Примеры

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

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

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

Зоомагазин#27083

В зоомагазине нужно расставить в один ряд клетки с животными. В ряд помещается N клеток, при этом есть одно ограничение: нельзя ставить рядом две клетки с собаками (иначе они передерутся). Предполагается, что в магазине есть неограниченное количество клеток с разными животными. Определите, сколькими безопасными способами можно расставить N клеток в ряд.

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

Входная строка содержит одно натуральное число – количество клеток в ряду N .

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

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

Ввод	Вывод
5	13

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

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

Кузнечик-KMax#27081

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 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

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

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

Кузнечик-K#27080

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 ≤ N , K ≤ 32 .

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

Программа должна вывести одно число: количество способов, которыми Кузнечик может добраться до столбика с номером N .

Ввод	Вывод
5 4	8

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

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

Кузнечик#27079

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть на следующий столбик или сразу на второй столбик, считая от текущего. Требуется найти количество способов, которыми Кузнечик может добраться до столбика с номером N . Учитывайте, что Кузнечик не может прыгать назад.

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

Входная строка содержит натуральное число N ( 1 ≤ N ≤ 45 ).

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

Ввод	Вывод
3	2
10	55

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

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

Сумма штрафа#27078

Новый градоначальник города Глупова решил с целью пополнения бюджета и экономии горючего провести кампанию борьбы с левым уклоном и левыми рейсами. Для этого он запретил водителям выполнять левые повороты, установив штраф за каждый поворот налево в размере одного миллиона (разворот поворотом налево не считается).

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

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

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

В первой строке вводится целое число N - количество записанных пар координат (\(1 <= N <= 1000\)). В каждой из следующих N строк записана очередная из этих пар (вещественные числа).

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

Выведите суммарный штраф водителя в миллионах.

Примеры

№	Входные данные	Выходные данные
1	4 0 0 1 0 1 1 2 1	1

Вычислительная геометрия

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

В каком ухе жужжит?#27077

Фрекен Бок находится в точке \(A(x_a, y_a)\) и, глядя прямо на Малыша, стоящего в точке \(B(x_b, y_b)\) задает вопрос: «В каком ухе у меня жужжит?». Естественно, у грозной домоправительницы жужжит в ухе, потому что в точке \(C(x_c, y_c)\) завис Карлсон со включенным мотором. Определите, какой ответ Малыша будет правильным.

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

С клавиатуры вводятся координаты точек A, B и С. Исходные данные являются целыми числами, по модулю не превышающими 1000.

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

Выведите слово LEFT (заглавными буквами), если у домоправительницы жужжит в левом ухе, RIGHT – если в правом, BOTH – если жужжание и в левом и в правом одинаково.

Примеры

№	Входные данные	Выходные данные
1	0 0 1 0 0 1	LEFT

Вычислительная геометрия

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

Принадлежит ли точка углу#27076

Дан угол AOB (O - вершина угла, A и B - точки на сторонах) и точка P. Определите, принадлежит ли точка P углу AOB (включая его стороны: лучи OA и OB).

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

Программа получает на вход координаты точек A, O, B, P. Все координаты - целые, не превосходят 100 по модулю. Точки A, O, B не лежат на одной прямой.

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

Программа должна вывести слово YES или NO.

Ввод	Вывод
0 1 0 0 1 0 1 1	YES

геометрия Элементарная геометрия

✓ 296✗ 1 544700средняяВойти и решать

Принадлежность точки лучу#27075

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

Шесть чисел – координаты точки и координаты начала и конца вектора.

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

Одна строка “YES”, если точка принадлежит лучу, определяемому вектором, и “NO” в противном случае.

Примеры

№	Входные данные	Выходные данные
1	4 0 4 2 4 5	NO

Вычислительная геометрия

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

МАРШРУТЫ#27073

В государстве Чудаков N городов ( 2 <=N <= 16 ), обозначаемых заглавными латинскими буквами, начиная с A, по порядку. Между некоторыми из них проложены дороги, которые могут быть как односторонними, так и двусторонними, причем не обязательно, что из каждого города можно проехать в любой другой.

В государстве всего один маршрут автобуса – 'Ч', который совершает только один рейс каждый день. Выходя из некоторого города, он совершает ровно N переездов между городами так, чтобы вернуться в тот, из которого выехал. Других ограничений на его маршрут нет. В течение дня автобус может несколько раз проезжать один и тот же город или дорогу. В каждом городе существуют автобусные парки, из которых могут выезжать автобусы маршрута 'Ч'. Так что, хотя автобус каждый день возвращается в город, из которого стартовал в этот день, на следующий день начало маршрута 'Ч' может быть из любого другого города. Но рейс каждый день только один.

Маршрут обозначается N буквами, начиная с города, из которого происходит выезд. Например, BCDCE – допустимый маршрут для государства из 5 городов ссоответствующими дорогами: выехать из B, проехать в C, затем в D, вернуться в C, проехать в E и вернуться в изначальный город B (последний пункт маршрута, совпадающий с первым, в маршруте не указывается).

Маршрут автобуса меняется каждый день так, что список маршрутов по дням расположен в словарном порядке и содержит все возможные маршруты. Когда список кончается, его обход начинается сначала. В первый день введения маршрута 'Ч' автобус шёл по первому по порядку маршруту. Выведите его маршрут на день K работы маршрута. Пример: В государстве четыре города: A, B, C, D. Наличие дорог между ними задано матрицей, где элемент равен 1, если из города, соответствующего строке, в город, соответствующий столбцу, есть дорога, и 0 – иначе (на главной диагонали нули – дорог, ведущих назад в тот же город, не бывает).

откуда/куда	A	B	C	D
A	0	0	1	1
B	1	0	1	1
C	0	1	0	0
D	0	1	1	0

Полное расписание маршрутов в таком государстве выглядит так:
ADCB
BADC
BCBC
BCBD
BDBC
BDBD
CBAD
CBCB
CBDB
DBCB
DBDB
DCBA

Таким образом, например, маршрут на день 30 – это BDBD.

Формат входных данных
В первой строке указывается количество городов N ( 2<= N <= 16 ). Далее следует N строк по N элементов (цифр), разделенных пробелом, содержащих матрицу, задающую дороги между городами. Далее следует строка содержащая целое число D – номер дня, маршрут которого требуется определить ( 1<= D <= 2⁶⁴ ).

Формат выходных данных
В единственной строке указывается маршрут, т.е. порядок посещения городов, например BDBD (см. предыдущий пример).

Ввод	Вывод
3 0 1 1 1 0 1 1 1 0 4	BCA

Комбинаторика

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

КОЛОНИЗАЦИЯ МАРСА#27072

Ученым удалось отправить на планету Марс мини-фабрику, которая может за одни сутки произвести мини-фабрику или дрона для сбора воды (мини-фабрика или дрон для сбора воды могут начать работу только со следующих суток). Дрон собирает одну единицу воды за одни сутки. Определите, за какое минимальное количество суток удастся собрать не менее N единиц воды.

Формат входных данных
Задается одно число N ( 1<= N <= 10⁹ ) – необходимое количество воды.

Формат выходных данных
Одно целое число M – минимально необходимое количество суток.

Ввод	Вывод
2	3

Замечание
Одна из правильных последовательностей действий выглядит так:
? В первые сутки мини-фабрика производит дрона для сбора воды;
? За вторые сутки мини-фабрика производит еще одного дрона, а первый дрон собирает одну единицу воды;
? За третьи сутки мини-фабрика может произвести еще одного дрона или мини- фабрику, при этом первый дрон собирает еще одну единицу воды (итого он собрал 2 единицы воды), а второй дрон собирает единицу воды. Таким образом, накоплено 3 единицы воды за трое суток.

Другая последовательность действий состоит в том, чтобы за первые сутки построить еще одну мини-фабрику, а за вторые сутки произвести двух дронов, которые на третьи сутки соберут 2 единицы воды.

Задача на реализацию

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

ПИРАМИДА#27071

Для строительства двухмерной пирамиды используются прямоугольные блоки, каждый из которых характеризуется шириной и высотой. Можно поставить один блок на другой, только если ширина верхнего блока строго меньше ширины нижнего. Самым нижним в пирамиде может быть блок любой ширины.

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

Формат входных данных
В первой строке входных данных задается число N – количество блоков ( 1 <= N <= 100000 ). В следующих N строках задаются пары целых чисел w_i и h_i ( 1<= w_i , h_i <= 10⁹), разделенные пробелом – ширина и высота блока, соответственно.

Формат выходных данных
Целое число – максимальная высота пирамиды.

Ввод	Вывод
3 3 1 2 2 3 3	5

Замечание.
В приведенном примере пирамида будет состоять из двух блоков: нижним будет блок с номером 3, а верхним – блок с номером 2. Блок с номером 1 нельзя использовать для строительства пирамиды, т.к. его ширина совпадает с шириной нижнего блока.

Использование сортировки

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

Кузнечик собирает монеты#27069

На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.

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

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

- в первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик;
- во второй строке выводится число прыжков Кузнечика;
- в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).

Если правильных ответов несколько, выведите любой из них.

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

✓ 404✗ 1 227700средняяВойти и решать

Capybara. Канатная дорога#27068

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

Известно, что лес состоит из n деревьев, стоящих в ряд и пронумерованных слева направо числами от 1 до n. Высота i-го дерева, по воспоминаниям Васи, равна h_i. Канатная дорога длины k должна опираться на k (1 <= k <= n) деревьев i₁, i₂, . . . , i_k (i₁ < i₂ < . . . < i_k), таких что их высота возрастает, то есть, h_i1 < h_i2 < . . . < h_ik.

Петя тоже был в лесу, и у него есть q предположений о том, где именно ошибается Вася. Его i-е предположение задаётся числами a_i и b_i , означающими, что, по мнению Пети, высота дерева

с номером a_i на самом деле равна b_i . Обратите внимание, Петины предположения независимы между собой.

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

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

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

Первая строка входных данных содержит два числа n и m (1 <= n, m <= 400 000) — количество деревьев в лесу и количество предположений Пети соответственно.

В следующей строке содержатся n целых чисел h_i (1 <= h_i <= 10⁹ ) — высоты деревьев по предположению Васи.

Каждая из следующих m строк содержит по два целых числа a_i и b_i (1 <= a_i <= n, 1 <= b_i <= 10⁹ ).

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

Для каждого предположения Пети выведите в отдельной строке одно число — максимальную длину канатной дороги.

Ввод	Вывод
4 4 1 2 3 4 1 1 1 4 4 3 4 5	4 3 3 4
4 2 1 3 2 6 3 5 2 4	4 3

Замечание

Рассмотрим первый пример. Первое Петино предположение совпадает с предположением Васи.

Согласно его второму предположению, высоты деревьев были (4, 2, 3, 4), третьему (1, 2, 3, 3), а по четвёртому предположению — (1, 2, 3, 5).

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

✓ 1✗ 411 300средняяВойти и решать

Возрастающая подпоследовательность#27052

Даны N целых чисел X₁, X₂, ..., X_N. Требуется вычеркнуть из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.

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

В первой строке находится число N. В следующей строке - N чисел через пробел. 1 <= N <= 10 000, 1 <= X_i <= 60 000.

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

В первой строке выводится количество невычеркнутых чисел, во второй - сами невычеркнутые числа через пробел в исходном порядке. Если вариантов несколько, вывести любой.

Примеры

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

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

✓ 221✗ 1 024700средняяВойти и решать

Числовая последовательность - 5#27050

Вычислить

\(P = (1 + \sin 0.1 ) \cdot (1 + \sin 0.2 ) \cdot ...\cdot (1 + \sin 1 )\)

Входные данные
Нет.

Выходные данные
Вывести число P.

Циклы

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

Числовая последовательность - 4#27049

Дано вещественное число х. Вычислить

\(s = {{(x-1)\cdot(x-3)\cdot(x-7)\cdot...\cdot(x-63)}\over{(x-2)\cdot(x-4)\cdot(x-8)\cdot...\cdot(x-64)}}\)

Входные данные
Вводится вещественное число х (-50 <= х <= 50). Гарантируется, что для заданного х решение существует.

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

Циклы

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

Числовая последовательность - 3#27048

Дано натуральное число N, вещественное число А. Вычислить

\(S = {{1 \over A} + {1 \over {A^2}} + {1 \over A^4} +... + {1 \over A^{2\cdot N - 2}} }\)

Входные данные
В первой строке вводится натуральное число N (0 < N <= 10). Во второй строке вводится вещественное число А (-5 <= А<= 5, А!=0).

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

Циклы

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

Числовая последовательность - 2#27047

Дано натуральное число N, вещественное число А. Вычислить

\(P = A \cdot (A - N) \cdot (A - 2 \cdot N) \cdot...\cdot (A - N^2)\)

Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-10<=А<=10).

Выходные данные
Вывести число P.

Циклы

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

Числовая последовательность - 1#27046

Дано натуральное число N, вещественное число А. Вычислить

\(P = A \cdot (A + 1) \cdot...\cdot (A + N - 1)\)

Входные данные
В первой строке вводится натуральное число N (0<N<=10). Во второй строке вводится вещественное число А (-100<=А<=100).

Выходные данные
Вывести число P.

Циклы

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