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

Минимизируем число#48942

У Незнайки есть одно натуральное четырехзначное число. Он решил подарить его Гуньке. Но, так как Гунька любит минимальные числа, Незнайке нужно составить из цифр его числа новое число, чтобы оно было как можно меньше. Помогите Незнайке составить из цифр его числа новое число, чтобы оно было минимальным.
Заметим, что четырехзначные числа не могут начинаться с нуля.

Формат входных данных
Вводится натуральное четырехзначное число.

Формат выходных данных
Выведите минимальное натуральное четырехзначное число, состоящее из тех же цифр.

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

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

Гласная подстрока#48030

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

Формат входных данных
Программа получает на вход строку s (10 <= s <= 10⁶). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z). Гласные буквы английского алфавита: AEIOUY.

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

Поиск подстроки в строке Строки

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

Самая длинная подстрока#48025

Дана строка s Определите длину самой длинной подцепочки, состоящей из одинаковых символов. В ответе укажите сначала символ, из которого строится данная подцепочка, затем, слитно без разделителей, длину данной подцепочки. Если таких подцепочек несколько, то укажите ту, в которой буква стоит раньше в алфавите.

Формат входных данных
Программа получает на вход строку s (10 <= s <= 10⁶). Строка состоит из символов английского алфавита, записанных в верхнем регистре (от A до Z).

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

ЕГЭ_информатика Поиск подстроки в строке Строки

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

Все сочетания из n по k#47937

Даны два целых числа n и k, выведите все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Порядок элементов в одной комбинации не важен. То есть комбинация (1, 2, 3) и (3, 2, 1) считается одинаковой.
Выведите на экран все такие комбинации в лексикографическом порядке.

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

Ограничения

1 <= n <= 20
1 <= k <= n

Выходные данные
Выведите в лексикографическом порядке все возможные комбинации из k чисел, выбранных из диапазона [1, n]. Каждая комбинация чисел должна выводиться в отдельной строке, числа в одной комбинации разделяются одним пробелом.

Перебор с возвратом Рекурсия

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

0-1 Рюкзак#47745

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

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

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

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

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

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

Раздвоитель#47701

Исполнитель “Раздвоитель” преобразует натуральные числа. У него есть две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке).

Выходные данные
Напишите алгоритм для Развоителя, который преобразует число A в число B и при этом содержит минимальное число команд. Команды алгоритма нужно выводить по одной в строке, первая команда обозначается, как -1, вторая команда как :2.

Примеры

№	Входные данные	Выходные данные
1	21 2	-1 :2 :2 -1 :2

Жадный алгоритм Линейные алгоритмы

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

Степень двойки#47700

Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.

Операцией возведения в степень пользоваться нельзя!

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

Вводится натуральное число N (N < 10⁹).

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

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

Примеры

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

Двоичная система счисления Цикл for

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

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

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

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

Ограничения

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

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

Примеры

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

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

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

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

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

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

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

Маршрут максимальной стоимости#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✗ 479500лёгкаяВойти и решать