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

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

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

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

XOR-cумма массива#47936

XOR-cумма массива определяется как побитовое XOR всех его элементов или 0, если массив пуст.

Например, XOR-сумма массива [2,5,6] равна 2 XOR 5 XOR 6 = 1.
Для заданного массива nums, верните сумму всех XOR-сумм для каждого подмножества nums.

Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз.
Массив a является подмножеством массива b, если a может быть получено из b путем удаления некоторых (возможно не удалением никаких) элементов b.

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

Ограничения

1 <= n <= 12
1 <= nums_i <= 20

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

Пояснения к тестовым примерам
В первом примере
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

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

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

Гирьки: четыре кучки#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.

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

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

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

Гармоничная последовательность lite - 2#47740

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, ..., a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3=a_2+a_4, ..., a_{n-1}=a_{n-2}+a_n\). Например, последовательность [1,2,1,–1] является гармоничной, поскольку 2=1+1, и 1=2+(–1) .

Рассмотрим последовательности равной длины: \(A=[a_1,a_2, ... a_n]\) и \(B=[b_1,b_2, ... b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A,B)= |a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|\) . Например, \(d([1,2,1,–1][1,2,0,0])=|1–1|+|2–2|++|1–0|+|–1–0|=0+0+1+1=2 \)

В конце лекции профессор написал на доске последовательность из n целых чисел \(B=[b_1,b_2, ... b_n]\)и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A=[a_1,a_2, ... a_n]\), такую, что \(d(A, B)\) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A,B)\) .

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Входные данные
Первая строка содержит целое число n – количество элементов в последовательности ( \(3 \le n \le 500\)).
Вторая строка содержит n целых чисел \(b_1, b_2, …, b_n (–100 \le b_i \le 100 )\) .

Выходные данные
Выведите одно целое число: минимальное возможное расстояние от исходной до гармоничной последовательности.

Примеры

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

Перебор

—Войти и решать

Раздвоитель#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

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

Слияние списков#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

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

✓ 131✗ 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.

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

Примеры

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

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

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

Счетовод - 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

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

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