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

Черепаха#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средняяВойти и решать

ПИРАМИДА#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 нельзя использовать для строительства пирамиды, т.к. его ширина совпадает с шириной нижнего блока.

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

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

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

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

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

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

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

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

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

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

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

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

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средняяВойти и решать

Тяжелая, вариант-2#27065

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

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

Гарантируется, что машины не пересекаются между собой, а также со стенами, но возможно соприкасаются.

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

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

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

Пример входных и выходных данных

Ввод	Вывод	Примечание
4 21 1 1 7 12 3 16	1
4 30 3 1 24 5 11 18	1
2 20 3 1 7 10	0	В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину.

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

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

Легкая, вариант-2#27063

Ваша задача — написать программу, которая определит время следующего резервного копирования после начала смены Ильи Филипповича. Считается, что резервное копирование происходит мгновенно. Таким образом, если Илья Филиппович заступает в момент резервного копирования, считается, что оно происходит уже в его смену.

Формат входного файла

На вход программе подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

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

Пример входных и выходных данных

Ввод	Вывод
12:55:00	13:00:00
00:00:00	00:00:00
18:30:03	19:00:00

Дата и время Задачи на моделирование

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

Легкая, вариант-1#27062

Сервер одной крупной аналитической компании делает резервное копирование всех данных каждые пол часа. Системный администратор Илья Филиппович Яковлев заступит сегодня на смену в известное время. Он знает, что сервер делает резервное копирование в полночь (00:00:00), но не может посчитать, когда же было последнее резервное копирование на момент его заступления на смену.

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

Формат входного файла

На вход программы подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

Требуется вывести время последнего резервного копирования в аналогичном формате.

Пример входных и выходных данных

Ввод	Вывод
12:55:00	12:30:00
00:00:00	23:30:00
18:30:03	18:30:00

Дата и время Задачи на моделирование

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

Возрастающая подпоследовательность#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

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

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

Линейная классификация#27044

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

день, а также информация о том, является ли этот аккаунт спам-ботом. Возраст аккаунта мы можем взять за X координату точки, а количество сообщений за Y

коордианату. Задача классификации состоит в том, чтобы провести какую-либо прямую так, чтобы объекты одного типа находились по одну сторону этой прямой, а объекты другого типа по другую.

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

Вам необходимо по информации о параметрах и типе объектов определить, существует ли прямая, которая однозначно разделеят классы объектов. Прямая не должна проходить ни через один объект.

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

В этой задаче входной файл содержит несколько тестовых блоков.

В первой строке задано число T количество тестовых блоков (1 <= T <= 100).

Каждый тестовый блок состоит из числа N количество описанных объектов (1 <= N <= 2000).

В следующих N строках содержится описания объектов, состоящие из трех целых чисел X, Y , Type (0 <= X, Y <= 10⁷, 0 <= Type <= 1).

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

Выведите T слов "YES" или "NO" по одному в строке для каждого из тестовых блоков. "YES" необходимо выводить если разделение на классы возможно, "NO" если невозможно.

Система оценки

Решения, верно работающие при T <= 10, N <= 100, будут набирать не менее половины баллов.

Ввод	Вывод
2 6 1 1 1 1 2 1 1 3 0 2 1 1 2 2 0 3 1 0 6 1 3 0 2 2 0 1 2 1 3 1 1 2 1 1 1 1 0	YES NO

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

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

Пираты!#27043

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

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

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

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

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

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

В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000) количество строк и столбцов на игровом поле.

Во второй строке записано натуральное число K (1 <= K <= 500) количество пиратских баз.

В следующих K строках записаны пары чисел R_i , C_i (1 <= R_i <= N, 1 <= C_i <= M) координаты пиратских баз (строка, столбец).

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

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

Система оценки

Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод	Вывод
10 10 4 2 2 5 3 5 9 8 8	3

Замечание

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

Двумерные массивы Использование сортировки

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