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

Ферзь в угол#48821

В левом верхнем углу доски размером NxM находится ферзь, который может двигаться только вправо-вниз. Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз, либо по горизонтали вправо, либо во диагонали вправо-вниз. Игрок, который не сможет сделать хода - проигрывает, иными словами, выигрывает игрок, который поставит ферзя в правый нижний угол. Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока.

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

Программа получает на вход два натуральных числа N и M, записанных в одной строке через пробел. Числа не превосходят 100.

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

Программа должна вывести номер игрока (1 или 2), у которого есть выигрышная стратегия.

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

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

Строковые артефакты#47938

Команда исследователей-археологов, отправилась в затерянный храм на поиски древних артефактов. На каждом артефакте записана строка, состоящая из символов "0" и "1". Археологи узнали, что выйти из храма с артефактами можно только в том случае, если суммарное количество нулей в строках, записанных на всех, взятых с собой артефактах, будет не больше m, а суммарное количество единиц не больше n. Исследователи хотят унести как можно больше артефактов. Ваша задача определить, какое максимальное количество артефактов исследователи-археологи смогут унести.

Входные данные
Первая строка содержит целое число k - количество артефактов в храме. Далее идут k строк s_i; в i-й строке записана строка с i-го артефакта, состоящая из "0" и "1".
На k+2 строке записаны 2 числа: m и n.

Ограничения

1 <= k <= 600
1 <= длина s_i <= 100
s_i состоит только из цифр '0' and '1'.
1 <= m, n <= 100

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

Пояснения к тестовым примерам
В первом тестовом примере наибольшим подмножеством, содержащим не более пяти 0 и не более трех 1, является {"10", "0001", "1", "0"}, поэтому ответ - 4.
Другие допустимые, но меньшие подмножества {"0001", "1"} и {"10", "1", "0"}.
Подмножества {"111001"} является недопустимым, так как содержит четыре 1, что больше n.

Задача о рюкзаке

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

Гирьки: четыре кучки#47780

Дан набор гирек массой m₁, …, m_N. Можно ли их разделить на четыре кучки равной массы?

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 14. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в четыре строки или строчку No solution, если решения не существует.

Задача о рюкзаке

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

Гирьки: три кучки одного размера#47749

Дан набор гирек массой m₁, …, m_N. Разделите его на три кучки равной масссы, содержащие равное число гирек.

Входные данные
Первая строка входных данных содержит натуральное число N, не превышающее 18. Далее идет N натуральных чисел mi, не превышающих 100.

Выходные данные
Программа должна вывести номера гирек для каждого из наборов в три строки или строчку No solution, если решения не существует.

Задача о рюкзаке

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

Сдача - 2#47748

Покупатель хочет приобрести товар стоимостью S рублей. У него есть N банкнот номиналом P₁, P₂, ..., P_N рублей. У продавца есть M банкнот номиналом Q₁, Q₂, ..., Q_M. рублей. Определите, смогут ли они рассчитаться.

Входные данные
Программа получает на вход сумму S. Далее идет число N затем P₁, P₂, ..., P_N. Далее идет число M, затем Q₁, Q₂, ..., Q_M.Количество банкнот у продавца и покупателя и их номиналы не превосходят 100.

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

Если они не могут рассчитаться, выведите число -1.

Задача о рюкзаке

✓ 1✗ 10—Войти и решать

Весы#47747

Если в продаже нет стандартного набора гирь, измерение массы становится большой проблемой. Ваш набор содержит n гирь массой 1 грамм, 4 грамма, 16 грамм, ..., 4^{n - 1} грамм. Кроме того, у вас есть две чаши весов. Чтобы взвесить объект, надо положить его на левую чашу весов и поставить некоторые гири на левую и правую чашу для достижения равновесия. Требуется найти, сколько целых масс в диапазоне [1; m ] возможно измерить, используя весы и данный набор гирь.

Входные данные
В единственной строке содержаться 2 целых числа m и n (1 ≤ n , m ≤ 10⁹ ) .

Выходные данные
Выведите одно число - количество масс, которые можно измерить с помощью этих гирь.

Задача о рюкзаке

✓ 1✗ 7—Войти и решать

0-1 Рюкзак#47745

Дано N предметов массой m₁, …, m_N и стоимостью c₁, …, c_N соответственно.

Ими наполняют рюкзак, который выдерживает вес не более M. Какую наибольшую стоимость могут иметь предметы в рюкзаке?

Входные данные
В первой строке вводится натуральное число N, не превышающее 100 и натуральное число M, не превышающее 10000. Во второй строке вводятся N натуральных чисел m_i, не превышающих 100. Во третьей строке вводятся N натуральных чисел с_i, не превышающих 100.

Выходные данные
Выведите наибольшую стоимость рюкзака.

Задача о рюкзаке

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

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

Путешествия Аркадия#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средняяВойти и решать