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

Призы#50361

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

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

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

Формат входных данных
Первая строка ввода содержит целая число \(n\) — количество призов (\(1 \le n \le 1000\)). Вторая строка содержит \(n\) чисел \(a_1, a_2, \ldots, a_n\) — стоимости призов в том порядке, в котором их покажут Мише (\(1 \le a_i \le 10^9\)).

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

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

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

Не подпоследовательность#50340

Последовательность \(X = [x_1, x_2, \ldots, x_t]\) является подпоследовательностью последовательности \(Y = [y_1, y_2, \ldots, y_s]\), если можно удалить некоторые (возможно ни одного) элементы \(Y\), чтобы получить \(X\). Иначе говоря, существует последовательность индексов \(1 \le i_1 < i_2 < \ldots < i_t \le s\), что \(x_j = y_{i_j}\) для всех \(j\) от \(1\) до \(s\). Например, последовательность \([1, 2, 3, 2]\) является подпоследовательностью последовательности \([\mathbf{1}, 1, \mathbf{2}, 2, 1, \mathbf{3}, \mathbf{2}, 1]\), а последовательность \([1, 2, 3, 1, 2]\) "— нет.

Рассмотрим две последовательности \(A = [a_1, a_2, \ldots, a_m]\) и \(B = [b_1, b_2, \ldots, b_n]\), состоящие из целых чисел от \(1\) до \(k\).

Требуется найти минимальную по длине последовательность \(C = [c_1, c_2, \ldots, c_p]\), которая не являлась бы подпоследовательностью ни \(A\) ни \(B\). Элементы последовательности \(C\) также должны являться целыми числами от \(1\) до \(k\).

Формат входных данных
Первая строка ввода содержит число \(k\) — максимальное значение элемента последовательности (\(1 \le k \le 5\,000\)).

Вторая строка содержит число \(m\) — длину последовательности \(A\) (\(1 \le m \le 5\,000\)). Третья строка содержит \(m\) целых чисел от \(1\) до \(k\) — последовательность \(A\).

Четвертая строка содержит число \(n\) — длину последовательности \(B\) (\(1 \le n \le 5\,000\)). Пятая строка содержит \(n\) целых чисел от \(1\) до \(k\) — последовательность \(B\).

Формат выходных данных
На первой строке выведите \(p\) — длину искомой последовательности. На второй строке выведите последовательность \(C\). Если оптимальных ответов несколько, выведите любой из них.

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

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

Непростые разбиения#50276

Рассмотрим разбиения целого положительного числа \(n\) в сумму целых положительных чисел. Будем называть разбиение непростым, если слагаемые в нем упорядочены по неубыванию, причем среди слагаемых нет простых чисел.

Например, для \(n=5\) существует два непростых разбиения: \(1+1+1+1+1\) и \(1+4\).

Задано число \(n\). Выведите все его непростые разбиения на слагаемые.

Формат входных данных
На вход подается число \(n\) (\(1 \le n \le 70\)).

Формат выходных данных
Выведите все непростые разбиения \(n\) на слагаемые. Слагаемые разделяйте знаком <<+>>. Не выводите пробелы. Разбиения можно вывести в любом порядке.

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

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

Разбиение на тройки#48972

На день рождения Маше как обычно подарили массив \(a\) из \(n\) натуральных чисел, в котором каждое число находится в пределах от \(1\) до \(m\) включительно. Маша очень любит число три, поэтому длина массива делится на три.

Маша решила объединять числа в тройки: каждая тройка чисел должна состоять или из трех одинаковых чисел, или из трех последовательных чисел. Другими словами, каждая тройка имеет или вид \((x, x, x)\), или \((x, x+1, x+2)\), где \(x\) — какое-то натуральное число.

Маша хочет поиграть с подаренным массивом, и ее интересует количество способов разбить числа этого массива на такие тройки. Два способа разбиения считаются различными, если нельзя установить взаимно-однозначное соответствие между тройками первого разбиения и тройками второго разбиения, что числа внутри соответствующих троек равны. Так как количество разбиений может быть большим, Маше достаточно знать его остаток по модулю \(10^9+7\).

Помогите Маше посчитать количество способов разбить числа подаренного ей массива на тройки по модулю \(10^9+7\).

Формат входных данных
Первая строка входных данных содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 5000\), \(1 \le m \le 5000\), \(n=3\cdot k\) для какого-то натурального \(k\)).

Вторая строка содержит \(n\) целых чисел \(a_i\) — числа массива (\(1 \le a_i \le m\)).

Формат выходных данных
В единственной строке одно число — количество способов разбить числа массива на тройки по модулю \(10^9+7\).

В первом примере числа можно разбить на тройки двумя способами: {\((2, 2, 2)\), \((3, 3, 3)\), \((4, 4, 4)\)} и {\((2, 3, 4)\), \((2, 3, 4)\), \((2, 3, 4)\)}.

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

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

Игра с таблицей#48967

Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);
выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

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

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

В первой строке выведите строку <<YES>>.
Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).
В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}\)

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}\)

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

В третьем примере изначально дана таблица:

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}\)

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}\)

meet in the middle Битовые операции

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

Пазл#48921

Участникам, использующим язык Python3, рекомендуется отправлять решения на проверку с использованием интерпретатора PyPy3.

Школьники Алиса и Ибрагим — лучшие друзья. У Ибрагима скоро день рождения, и по этому поводу Алиса решила подарить ему новый пазл. Пазл можно представить в виде матрицы из \(2\) строк и \(n\) столбцов, каждый элемент которой \(0\) или \(1\). За один ход можно поменять местами два элемента, стоящие в соседних клетках.

Более формально, будем считать, что строки матриц пронумерованы сверху вниз от \(1\) до \(2\), а столбцы — слева направо от \(1\) до \(n\). Обозначим клетку на пересечении строки \(x\) и столбца \(y\) за \((x, y)\). Будем считать две клетки \((x_1, y_1)\) и \((x_2, y_2)\) соседними, если \(|x_1 - x_2| + |y_1 - y_2| = 1\).

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

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

Формат входных данных
В первой строке вводится одно целое число \(n\) (\(1 \leq n \leq 200\,000\)) — количество столбцов в пазле.

Следующие две строки описывают рисунок, образованный пазлом в данный момент. В каждой строке вводятся \(n\) целых чисел, каждое из которых равно \(0\) или \(1\).

Следующие две строки описывают желаемый рисунок Алисы в том же формате.

Формат выходных данных
Если Алиса не ошиблась и её рисунок можно получить, найдите и выведите минимальное необходимое количество ходов, иначе выведите \(-1\).

В первом примере из условия подойдет следующая последовательность обменов:

\((2, 1), (1, 1)\)

\((1, 2), (1, 3)\)

\((2, 2), (2, 3)\)

\((1, 4), (1, 5)\)

\((2, 5), (2, 4)\)

Можно показать, что меньшим числом обменов обойтись нельзя, поэтому ответ равен \(5\).

Во втором примере из условия никакая последовательность ходов не приводит пазл к нужному виду.

Динамическое программирование Жадный алгоритм Паросочетания

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

Ферзь в угол#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.

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

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

✓ 35✗ 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

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

✓ 71✗ 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✗ 202600лёгкаяВойти и решать

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

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

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

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

Примеры

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

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

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