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

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

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

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

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

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

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

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

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

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

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

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

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

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

Формальное исполнение алгоритма, заданного на естественном языке или для конкретного исполнителя с заданным набором команд#27036

Цепочки цифр (строки) создаются по следующему правилу:

Первая строка состоит из двух цифр «1».

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

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

Вот первые 4 строки, созданные по этому правилу:

(1) 11

(2) 21212

(3) 32313231323

(4) 43424341434243414342434

Таким образом, было построено еще 5 строк и в результате получена строка, содержащая цифры от 1 до 9 и состоящая из 767 цифр.

Напишите через пробел сначала цифру, стоящую на a позиции от начала, а затем на b позиции от начала. a и b считываются с клавиатуры (записаны в одной строке через пробел, номер позиции от начала отсчитывается с 1).

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

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

Рекурсивный DFS#27034

Дана матрица N (1 <= N <= 100) на M (1 <= M <= 100). В матрице имеются ‘.’ – пустые клетки и ‘#’ – клетки, которые нельзя посетить. Ходить можно только вверх, вниз, влево и вправо. Дано q запросов: номер строки и номер столбца, если эта клетка – ‘#’, то она станет ‘.’, иначе – ‘#’. Для каждого из q запросов определить, достижима ли из клетки (S_x; S_y) клетка (t_x; t_y). Вывести на каждой строчке “Yes”, если достижима, и “No” - иначе.
Гарантируется, что клетка (S_x; S_y) и клетка (t_x; t_y)не являются ‘#’ клеткой в каждом запросе.

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

На первой строчке вводятся числа S_x (1 <= S_x <= 100), S_y (1 <= S_y <= 100), t_x (1 <= t_x <= 100), t_y (1 <= t_y <= 100), N (1 <= N <= 100), M(1 <= M <= 100) и q (1 <= q <= 100). На следующих N строках дается матрица, где ‘.’ – пустая клетка и ‘#’ – клетка, которую нельзя посетить. На следующих q строках дан номер строки и номер столбца, которые надо изменить.

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

Вывести на каждый из q запросов “Yes”, если из клетки (S_x; S_y) в клетку (t_x; t_y) можно попасть, “No” – иначе.

Пояснение
В тестовом примере после первого запроса матрица будет такой:

..#

##.

###

Из точки (1; 1) в (2; 3) нет прохода, следовательно, выводим “No”.

После второго запроса матрица будет такой:

..#

#..

###

Из точки (1; 1) в (2; 3)есть проход, следовательно, выводим “Yes”. Выделен путь, по которому мы сможем идти.

Обход в глубину

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

Алгоритмизация и программирование#27032

Дана исходная последовательность цифр: 1234
Задан алгоритм преобразования последовательности, на каждом шаге которого выполняются следующие операции:
1. В конец последовательности, имеющейся перед выполнением шага, дописывается ее копия, но развернутая зеркально (цифры записываются в обратном порядке).
2. В конце получившейся последовательности удаляется количество цифр, равное номеру шага выполнения алгоритма.

Ниже приведены результаты выполнения первых двух шагов алгоритма:
1: 1234432
2: 123443223443

Определите, какие цифры будут на A-ой, B-ой и C-той позиции от начала последовательности, которая получилась после выполнения 8-ого шага алгоритма. В ответе укажите через пробел три цифры: сначала цифру, которая стоит на А-ой позиции, затем цифру, которая стоит на В-ой позиции и затем цифру, которая стоит на С-той позиции. A, B и C задаются с клавиатуры.

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

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

27031#27031

Сколько существует таких натуральных чисел в диапозоне от a до b, что их запись в шестнадцатеричной системе счисления будет иметь ровно две значащих цифры, а в восьмеричной системе счисления – ровно три значащих цифры?

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

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

Обратная перестановка#27019

По данной перестановке π требуется найти π^-1.

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

В первой строке входных данных содержится число 0 < N <= 20000 – количество элементов в перестановке π. Во второй строке записана сама перестановка π.

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

Выведите π^-1

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

Разбор:
Вводим N и заводим массив от 1-го до N. Теперь начинаем считывать данную перестановку - хранить ее не обязательно, поэтому разумно будет вводить каждый элемент в одну и ту же переменную. Вводя i-й элемент кладем его порядковый номер (i) в ячейку массива с номером, равному этому числу, т.е. для каждого элемента данной перестановки сохраняем его место в этой перестановке. Теперь выводим полученный массив.

Алгоритмы обработки Перестановки

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

Алгоритм#27016

Реализуйте на одном из языков программирования алгоритм, представленный на схеме.

В первой строке ввода содержатся два целых числа A и B (1 ≤ A ≤ B ≤ 10⁹).

Вывести одно целое число – значение K после завершения работы алгоритма.

Ввод	Вывод
10 100	2

Задачи на моделирование Цикл for

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

Дипломы#25961

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек. Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Входные данные: на вход подаются три целых числа: w, h, n (\(1<=w,\ h,\ n <= 10^9\) ).

Выходные данные: необходимо вывести ответ на поставленную задачу.

Примеры

№	Входные данные	Выходные данные
1	2 3 10	9
2	1 1 1	1

Бинарный поиск по ответу

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

Левый и правый двоичный поиск#25960

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

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

В первой строке входных данных записано два числа N и M (\(1<=N,\ M <=20000\)). Во второй строке записано N упорядоченных по неубыванию целых чисел — элементы первого списка. В третьей строке записаны M целых неотрицательных чисел - элементы второго списка.
Все числа в списках - целые 32-битные знаковые.

Формат входных данных
Программа должна вывести M строчек. Для каждого числа из второго списка нужно вывести номер его первого и последнего вхождения в первый список. Нумерация начинается с единицы. Если число не входит в первый список, нужно вывести одно число 0.

Бинарный поиск в массиве

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

Слажал - отжался#25917

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

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

В первой строке число содержится число N (2 <= N <= 1000) количество детей в классе. В

следующей строке записана исходная расстановка школьников: N чисел через пробел, i-е число

обозначает рост i-го школьника r_i (1 <= r_i <= 10⁹) в нанометрах.

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

Одно число суммарное количество отжиманий. Гарантируется, что школьники суммарно отожмутся не более 2 · 10⁹ раз.

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

Замечание

В примере школьники с ростом 1 и 2 поменяются местами и каждый отожмјтся по разу, затем школьники 1 и 3 (каждый отжимается 2 раза, суммарно плюс 4 отжимания), и последними школьники 2 и 3 (плюс 2 отжимания).

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

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

Это Бомба#24906

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

Инструкция:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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