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

Слияние списков#47668

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список.
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)).

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

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

Примеры

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

"Два указателя"Одномерные массивы

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

Идентичные строки#47639

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

Входные данные
Программа получает на вход две строки s1 и s2.

Ограничения

1 <= длина s1 и s2 <= 500;
s1 и s2 состоят из маленьких английских букв.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	sea eat	2	Вам нужно сделать один шаг, чтобы превратить "sea" в "ea", и еще один шаг, чтобы превратить "eat" в "ea".

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

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

Наименьшая сумма ASCII кодов#47638

Вам даны две строки s1 и s2. Вы можете удалить из обоих строк любое количество символов. Ваша цель сделать строки одинаковыми.
Найдите наименьшую сумму ASCII кодов всех удаленных символов.

Входные данные
Программа получает на вход две строки s1 и s2.

Ограничения

1 <= длина s1 и s2 <= 1000;
s1 и s2 состоят из маленьких английских букв.

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

Примеры

№	Входные данные	Выходные данные	Примечание
1	sea eat	231	Удаление "`s`" из слова "`sea`" добавляет к сумме ASCII код буквы "`s`" (115). Удаление буквы "`t`" из слова "`eat`" добавляет к сумме 116. В итоге обе строки равны, а `115 + 116 = 231` - минимально возможная сумма для достижения этой цели.

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

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

Эксперименты Шелдона#47569

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

Входные данные
Первая строка содержит натуральное число n - длина последовательности Шелдона. Вторая строка содержит n чисел - элементы последовательности (nums_i).

Ограничения

1 <= n <= 2000
-10⁶ <= nums_i <= 10⁶

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

Примеры

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

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

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

Василий собирает ягоды#47308

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

Входные данные
Программа получает на вход два целых числа N и K (N > 0, 0 ≤ K ≤ N, K<=10⁹, N<=2*10⁹), записанные в отдельных строках, — текущее количество ягод в корзинке медведя Василия и количество ягод малины в корзинке.

Выходные данные
Выведите единственное число — минимальное число ягод малины, которое необходимо собрать.

Примеры

№	Входные данные	Выходные данные	Примечание
1	27 7	3	В примере всего ягод в корзинке 27, из которых малины 7 ягод. Если в собрать ещё 3 ягоды малины, то в корзинке станет 30 ягод, из которых малины будет 10.

Бинарный поиск по ответу Вывод формулы Целые числа

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

Путешествия Аркадия#47162

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

Аркадий может купить билеты по разным тарифам:

1-дневный тариф стоит C1 рублей;
7-дневный тариф стоит C2 рублей;
30-дневный тариф стоит C3 рублей.

Каждый билет начинает действовать с того дня, когда был куплен.
Например, если Аркадий купит 7-дневный билет на 2-й день путешествия, то он сможет путешествовать 7 дней: 2, 3, 4, 5, 6, 7 и 8 дни.

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

Входные данные
Первая строка содержит натуральное число n - количество дней, в которые Аркадий планирует путешествовать. Вторая строка содержит порядковые номера дней, в которые Аркадий планирует путешествовать (days_i). Третья строка содержит три числа: C1, C2, C3.

Ограничения:

1 <= n <= 365
1 <= days_i <= 365
Порядковы номера дней days_i даются в строго возрастающем порядке.
1 <= С1, С2, С3 <= 1000

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

Примеры

№	Входные данные	Выходные данные
1	6 1 4 6 7 8 20 2 7 15	11
2	12 1 2 3 4 5 6 7 8 9 10 30 31 2 7 15	17

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

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

Рекурсия итеративно - 3#47159

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = n, если n < 11,

F(n) = n + F(n –1), если n ≥ 11

По заданным числам A и B вычислите значение выражения F(A) – F(B)?

Входные данные
А и B вводятся с клавиатуры (2000 <= A, B <= 5000). Каждое число в отдельной строке.

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

Примеры

№	Входные данные	Выходные данные
1	2023 2007	32248

Рекуррентные последовательности

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

Рекурсия итеративно - 2#47158

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 7, если n < 7,

F(n) = n + 1 + F(n –2), если n ≥ 7.

Примеры

№	Входные данные	Выходные данные
1	3000 2000	1251000

Рекуррентные последовательности

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

Рекурсия итеративно - 1#47155

Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:

F(n) = 3, если n < 3,

F(n) = 2n + 5 + F(n – 2), если n ≥ 3.

Примеры

№	Входные данные	Выходные данные
1	3000 2000	2503500

Рекуррентные последовательности

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

Счетовод - 8#47154

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь A

2. умножь на B

3. умножь на С

Первая из них увеличивает на A число на экране, вторая умножает число на экране на B, третья умножает число на экране на С. Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num и не содержит число misnum?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, B не равно C.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num, misnum (1<= A <= 10, 2 <= B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S <= num < misnum <= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 3 46 12 25	120

Рекуррентные последовательности

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

Счетовод - 7#47152

У исполнителя Счетовод две команды, которым присвоены номера:

1. вычти A

2. вычти B

3. подели на С

Первая из них уменьшает на A число на экране, вторая уменьшает число на экране на B, третья делит целочисленно число на экране на С (с отбрасыванием остатка, в случае, если число на экране не делится на С). Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num1 и число num2?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, A не равно B.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num1, num2 (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S >= num1 > num2 >= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 3 3 22 2 11 4	369

Рекуррентные последовательности

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

Счетовод - 6#47145

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь A

2. прибавь B

3. умножь на С

Первая из них увеличивает на A число на экране, вторая увеличивает число на экране на B, третья умножает число на экране на С. Программа для Счетовода – это последовательность команд. Сколько существует таких программ, которые исходное число S преобразуют в число F и при этом траектория вычислений программы содержит число num1 и число num2?

Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F, A не равно B.

Входные данные
Программа получает на вход семь чисел в следующем порядке: A, B, C, S, F, num1, num2 (1<= A,B,C <= 10, 1 <= S <= 100, 1 <= F <= 10³, S <= num1 < num2 <= F). Каждое число вводится с новой строки.

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 2 3 13 9 11	68

Рекуррентные последовательности

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

Счетовод - 5#47128

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь 1

2. сделай четное

3. сделай нечетное

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2, третья переводит число x в число 2x + 1. Например, вторая команда переводит число 10 в число 20, а третья переводит число 10 в число 21.
Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход два числа: S, F (1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

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

Рекуррентные последовательности

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

В фантастическом лесу#47118

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

creature[1] = 1
creature[2 * i] = creature[i], если 2 <= 2 * i <= n
creature[2 * i + 1] = creature[i] + creature[i + 1], при 2 <= 2 * i + 1 <= n

Чтобы понять, насколько могущественны существа в лесу, необходимо найти существо с максимальным уровенем энергии.

Входные данные
Программа получает на вход натуральное число n (1 <= n <= 100) - количество существ в фантастическом лесу.

Выходные данные
Выведите максимальный уровень энергии среди всех существ в данном фантастическом лесу.

Примеры

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

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

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

Го#47001

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

Входные данные
В первой строке записаны 2 натуральных числа N и M - размер доски для игры в Го. Следующие N строк содержат по M чисел a_i,j. Каждое число a_i,j= 1 если на этой клетке расположен черный камушек и 0, если на ней расположен белый камушек.

Ограничения

n == количество строк в матрице
m == количество столбцов в матрице
1 <= n, m <= 300
a[i][j] это 0 или 1.

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

Рисунок выше относится к примеру № 1

Примеры

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

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

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

Счетовод - 5#46804

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь 1

2. увеличь каждый разряд числа на 1

Первая команда увеличивает число на 1, вторая - увеличивает каждый разряд числа на 1, если он не равен 9.
Например, число 45 с помощью команды 2 превратится в 56, а 49 в 59 (так как младший разряд равен 9 и он остается без изменений).
Программа для Счетовода – это последовательность команд.
Сколько существует программ, которые число S преобразуют в число F?

Входные данные
Программа получает на вход два числа (каждое число записано в отдельной строке): S и F ( 1 <= S <= 100, 10 <= F <= 1000, S < F).

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	26 49	22

Рекуррентные последовательности

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

Счетовод - 4#46792

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь A

2. умножь на B

3. возведи в квадрат

Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, S, F (1 <= A, B <= 10, 1 <= S <= 100, 1 <= F <= 10³)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 2 38	266

Рекуррентные последовательности

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

Счетовод - 3#46791

У исполнителя Счетовод три команды, которым присвоены номера:

1. прибавь A

2. прибавь B

3. умножь на С

Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход четыре числа: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 10, 1 <= F <= 100, A и B - различные числа)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 1 12	225

Рекуррентные последовательности

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

Счетовод - 2#46790

У исполнителя Счетовод три команды, которым присвоены номера:

1. прибавь A

2. умножь на B

3. умножь на С

Программа для Счетовода – это последовательность команд. Сколько есть программ, которые число S преобразуют в число F?
Гарантируется, что имеется хотя бы одна программа, которая получает из числа S число F.

Входные данные
Программа получает на вход пять чисел: A, B, С, S, F (1 <= A, B, C <= 10, 1 <= S <= 100, 1 <= F <= 10³, B и C - различные числа)

Выходные данные
Выведите ответ на задачу. Гарантируется, что ответ не превышает 2⁶³.

Примеры

№	Входные данные	Выходные данные
1	1 2 3 1 18	96

Рекуррентные последовательности

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

Счетовод - 1#46789

У исполнителя Счетовод две команды, которым присвоены номера:

1. прибавь A

2. умножь на B

Примеры

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

Рекуррентные последовательности

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