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

По данному числу N выведите все строки длины N из нулей и единиц в лексикографическом порядке.

Входные данные
Задано единственное число N (натуральное, \(1 <= N <= 10\))

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

Примеры

№	Входные данные	Выходные данные
1	2	00 01 10 11

Перестановки

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

Все двоичные строки длины n, содержащие ровно k единиц#27088

По данным числам N и K выведите все строки из нулей и единиц длины N, содержащие ровно K единиц, в лексикографическом порядке.

Входные данные
Заданы 2 числа: N и K (\(0 <= K <= N\), \(0 <= N <= 100\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 2	0011 0101 0110 1001 1010 1100

Перестановки

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

Черепаха#27086

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

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

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

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

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

Примеры

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

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

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

Зоомагазин#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

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

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

Кузнечик-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лёгкаяВойти и решать

ПИРАМИДА#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 223700средняяВойти и решать

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

Конечный ряд чисел - 3#27045

Дано вещественное число X (X<10). Вычислить

Входные данные: в первой строке вводится единственное число Х

Выходные данные: Выведите сумму данного ряда
(В проверяющей программе установлена точность 3 знака после запятой)

Цикл for

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