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

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

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

Когда же поезд#46984

В глухом местечке под названием Элдстейд был маленький железнодорожный вокзал. Элдстейд славился своим уютным и тихим образом жизни. Именно здесь жили четверо друзей: Матильда, Кира, Жак и Винсент.

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

Матильда получила информацию, что поезд должен прибыть в определенный час. Однако, внезапно поступила новость о задержке поезда на несколько часов из-за погодных условий в соседнем округе.

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

Входные данные
Даны положительное целое число arrivaltime, обозначающее время прибытия поезда в часах, и другое положительное целое число delayedTime, обозначающее время задержки в часах. Каждое из чисел записано в отдельной строке.

Ограничения

0 <= arrivaltime < 24
1 <= delayedTime <= 24

Выходные данные
Выведите время прибытия поезда на станцию.

Обратите внимание, что время в этой задаче представлено в 24-часовом формате.

Примеры

№	Входные данные	Выходные данные
1	15 5	20
2	13 11	0

Целые числа

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

Праздник Времени#46983

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

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

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

имя состоит только из английских букв, различного регистра
1900 <= год рождения <= 2023

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

Примеры

№	Входные данные	Выходные данные
1	Alex 2010 Vika 2009 Max 2014 Liza 2012	Vika 5

Условный оператор

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

Приключения Максимуса#46945

Однажды Максимус услышал о загадочной пещере, которая находится на вершине высокой горы. Говорят, что в этой пещере скрывается невероятное сокровище. Максимус преодолевает опасности и достигает пещеры. Но в пещере его встречает Старец, который просит по заданным двум числам num и t назвать ему максимальное супер-число. Число x называется супер-числом, если его можно сделать равным num, применяя следующую операцию t раз:

увеличьте или уменьшите x на 1 и одновременно увеличьте или уменьшите num на 1.

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

Можно доказать, что существует хотя бы одно супер-число.

Входные данные
В первой строке записано число num, во второй - число t.

Ограничения

1 <= num, t <= 50

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

Примеры

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

Вывод формулы

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

Триспектакулярные числа#46944

Триспектакулярные числа - это числа, которые встречаются в каком-либо наборе чисел более чем в ⌊n/3⌋ число раз. В заданном наборе из n чисел, найдите все триспектакулярные числа этого набора.

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

Ограничения

1 <= n <= 5 * 10⁴
-10⁹ <= a[i] <= 10⁹

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

Примеры

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

Словари

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

Счетовод - 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лёгкаяВойти и решать

Задача Магистра Математикуса#46766

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

Если число четное, он может разделить его на 2.
Если число нечетное, он может увеличить его на 1 или уменьшить на 1.

Сегодня Магистр Математикус задумался над вопросом, какое минимальное количество операций ему необходимо выполнить для превращения числа n в 1 с использованием его волшебных способностей. Помогите ему ответить на этот вопрос.

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

Ограничения на входные данные

1 <= n <= 2³¹ - 1

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

Примеры

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

Рекурсия

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

Маршрут максимальной стоимости#46765

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

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

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

В первой строке записаны два числа N и M - размеры таблицы (1<=N<=100, 1<=M<=100). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

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

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

№	Входные данные	Выходные данные
1	5 5 9 9 9 9 9 3 0 0 0 0 9 9 9 9 9 6 6 6 6 8 9 9 9 9 9	74 D D R R R R D D

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

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

Магическая энергия - 2#46737

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

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

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел a_i - количество магической энергии в i-м доме.

Ограничения на входные данные

1 <= n <= 100
0 <= a[i] <= 1000
1 <= i <= n

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

Примеры

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

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

✓ 3✗ 35—Войти и решать

Магическая сила#46700

Вы - маг, странствующий по волшебному лесу, в поисках своей утраченной магической силы. Эта магическая сила находится в волшебных кристаллах, которые растут на деревьях в этом волшебном лесу. На каждом дереве растет только один волшебный кристалл. Так как вы маг, то вы знаете какой силой обладает тот или иной кристалл, растущий на определенном дереве в этом лесу. Вы хотите получить в этом лесу как можно больше магической силы. Для этого вам следует выполнить следующее действие любое количество раз:

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

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

Входные данные
Первая строка входных данных содержит число n - количество деревьев в волшебном лесу. Вторая строка содержит n чисел a_i - волшебная сила кристалла на i-м дереве.

Ограничения на входные данные

1 <= n <= 2 * 10⁴
1 <= a[i] <= 10⁴
1 <= i <= n

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

Примеры

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

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

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

Магическая энергия#46699

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

Зная уровень магической энергии в каждом доме, найдите максимальное количество магической энергии, которое вы можете собрать сегодня, избегая извлечения энергии из соседних домов в одну и ту же ночь. Кроме этого, определите заранее какие дома вы должны посетить?

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел a_i - количество магической энергии в i-м доме.

Ограничения на входные данные

1 <= n <= 100
0 <= a[i] <= 400
1 <= i <= n

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

Примеры

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

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

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