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

Паша и Тёма приехали преподавать в зимний ноутбучный университет. Теперь им необходимо разобраться с учениками.

Есть \(n\) учеников, пронумерованных от \(1\) до \(n\). Уровень знаний \(i\)-го ученика равен \(a_i\). Всех учеников нужно распределить на стабильные параллели. Параллель называется стабильной, если после сортировки всех учеников параллели в порядке возрастания их уровня знаний у любых двух подряд идущих учеников разница уровня знаний не превосходит \(x\).

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

Формат входных данных
В первой строке вводятся три целых числа \(n\), \(k\), \(x\) (\(1 \le n \le 200\,000, 0 \le k \le 10^{18}, 1 \le x \le 10^{18}\)) — количество учеников, сколько учеников можно пригласить дополнительно и максимальная допустимая разница уровня знаний.

Во второй строке вводится \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^{18}\)) — уровни знаний учеников.

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

Примечание

В первом примере из условия можно пригласить учеников с уровнями знаний, равными \(2\) и \(11\). Тогда учеников можно разделить на следующие стабильные параллели:

\([1, 1, 2, 5, 8, 11, 12, 13]\),
\([20, 22]\).

Во втором примере из условия новых учеников приглашать нельзя, поэтому потребуется \(3\) параллели:

\([1, 1, 5, 5, 20, 20]\)
\([60, 70, 70, 70, 80, 90]\)
\([420]\)

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

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

Вася и Петя#50403

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

Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло \(q\) вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции \(l\) до позиции \(r\) включительно. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке \(k\) раз, где \(k\) — порядковый номер соответствующей буквы в алфавите. Например, если Вася выбрал подстроку <<abbcb>>, то он повторит букву <<a>> один раз, каждую из букв <<b>> — по два раза, букву <<c>> — три раза, и полученная строка будет равна <<abbbbcccbb>>, ее длина равна 10. Вася интересуется именно длиной полученной строки.

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

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

Во второй строке дана строка \(s\) — сама песня, представляющая собой строку длины \(n\) из маленьких букв английского алфавита.

В следующих \(q\) строках даны описания вопросов. Каждое описание состоит из двух чисел \(l\) и \(r\) \((1 \leq l \leq r \leq n)\) — границы каждого из вопросов.

Формат выходных данных
Выведите \(q\) строк — для каждого вопроса выведите длину строки, которую выпишет Вася.

Примечание

В первом примере Васю интересуют три вопроса. В первом вопросе Вася рассматривает подстроку <<aba>>, которая превратится в <<abba>>, а значит, ответ на этот вопрос равен 4. Во втором вопросе Вася рассматривает подстроку <<baca>>, которая превратится в <<bbaccca>>, а значит, ответ на этот вопрос будет равен 7. В третьем вопросе Вася рассматривает всю строку <<abacaba>>, которая превратится в <<abbacccabba>> — строку длины 11.

Для получение номера буквы можно использовать следующий код:

В языке python3 или pypy3 выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.
В языке c++ выражение x - 96, например a - 96 равно 1, а x - 96 равно 24.
В языке pascal выражение ord(x) - 96, например ord(a) - 96 равно 1, а ord(x) - 96 равно 24.

Префиксные суммы(минимумы, ...)

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

Красивые перестановки#50397

Перестановкой размера \(n\) называется массив \(\langle a_1, a_2, \ldots, a_n \rangle\) различных чисел от \(1\) до \(n\). Каждое число в перестановке встречается ровно один раз.

Сеня называет красотой перестановки \(\langle a_1, a_2, \ldots, a_n \rangle\) число \((a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n)\). Он хочет посчитать количество перестановок, красота которых делится на \(k\).

Даны числа \(n\) и \(k\), найдите количество перестановок размера \(n\), красота которых делится на \(k\).

Например, для \(n = 3\) существует \(6\) перестановок. Рассмотрим все эти перестановки и их красоту.

Перестановка	Красота
\(\langle 1, 2, 3\rangle\)	\(1\cdot2 + 2\cdot3 = 8\)
\(\langle 1, 3, 2\rangle\)	\(1\cdot3 + 3\cdot2 = 9\)
\(\langle 2, 1, 3\rangle\)	\(2\cdot1 + 1\cdot3 = 5\)
\(\langle 2, 3, 1\rangle\)	\(2\cdot3 + 3\cdot1 = 9\)
\(\langle 3, 1, 2\rangle\)	\(3\cdot1 + 1\cdot2 = 5\)
\(\langle 3, 2, 1\rangle\)	\(3\cdot2 + 2\cdot1 = 8\)

Формат входных данных
Входные данные содержат два целых числа: \(n\) и \(k\) (\(1 \le n \le 10\), \(2 \le k \le 1000\)).

Формат выходных данных
Выведите одно целое число: количество перестановок размера \(n\), красота которых делится на \(k\).

Простые задачи на перебор

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

2024-type1-generation#50380

Определите наименьшее трехзначное число x, для которого истинно логическое выражение:

(x оканчивается на {1}) И НЕ (x < {2})

ОГЭ

900средняяВойти и решать

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

Фибоначчиевы суммы#50359

Числа Фибоначчи определяются следующим образом: \(F_1 = 1\), \(F_2 = 2\), а для \(n > 2\) выполнено \(F_n = F_{n - 2} + F_{n - 1}\). Таким образом, начало последовательности чисел Фибоначчи выглядит так \(1, 2, 3, 5, 8, 13, 21, \ldots\).

Вам заданы числа \(n\) и \(k\). Требуется найти все способы представить число \(n\) в виде суммы неубывающих чисел Фибоначчи, причем кажое число разрешается использовать не более \(k\) раз.

Формат входных данных
Первая строка ввода содержит число \(n\) (\(1 \le n \le 100\)).

Вторая строка ввода содержит число \(k\) (\(1 \le k \le 20\)).

Формат выходных данных
Выведите все искомые представления, по одному на строке. Разделяйте числа знаком <<+>>, не используйте пробелы.

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

Перебор с возвратом

✓ 4✗ 12—Войти и решать

Соседние цвета#50345

Этнограф изучает народ крайнего севера. Его заинтересовала структура бусов, которые составляются из бусин трех цветов: синего, зеленого и красного. Этнографу кажется, что частота, с которой определенные цвета встречаются у соседних бусин, позволяет сделать выводы о культуре народа.

Бусы можно задать в виде строки из заглавных английских букв: <<R>> для красной бусины, <<G>> для зеленой бусины и <<B>> для синей бусины. Соседние буквы в строке соответствуют соседним бусинам. Бусы находятся на круглой нитке, поэтому первая и последняя бусины также являются соседними.

Например, в ожерелье <<RGRGRGRG>> 8 раз рядом встречаются зеленая и красная бусины, а в ожерелье <<RRRR>> 4 раза рядом встречаются две красные бусины.

Помогите этнографу по образцам бусов выяснить, какая пара цветов встречается рядом чаще всего. Порядок цветов в паре не имеет значения.

Формат входных данных
На первой строке ввода находится чиcло \(n\) — количество бус в распоряжении этнографа (\(1 \le n \le 100\)).

На каждой из следующих строк находится строка из букв <<R>>, <<G>> и <<B>>. Длина каждой строки не меньше \(3\) и не больше \(1000\).

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

Алгоритмы обработки реализация

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

Сумма#50342

Даша очень любит представлять числа в виде суммы. Сегодня Даша хочет выписать все возможные представления числа \(n\) в виде суммы \(k\) слагаемых.

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

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

Формат входных данных
Первая строка ввода содержит число \(n\) (\(-15\le n \le 15\)).

Вторая строка содержит число \(k\) (\(1 \le k \le 15\)).

Гарантируется, что общее число представлений не превышает \(10^5\).

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

Простые задачи на перебор

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

Радиация#50339

Космический аппарат "Звезда" выполняет задачу по фиксации показаний уровня космической радиации. Каждое показание записывается в виде целого числа. В процессе первоначальной обработки данных, для устранения потенциально неточных результатов, убирают из списка K наибольших и K наименьших показаний.
Исходя из списка полученных показаний и количестве исключаемых показаний, определите самое высокое точное показание и целую часть среднего арифметического всех точных показаний.

Формат входных данных
В первой строке записаны два числа через пробел: N – общее количество показаний (натуральное число, не превышающее 10 000) и K – количество исключаемых минимальных и максимальных показаний. В следующих N строках находятся значений каждого показания (все числа натуральные, не превышающие 10000), каждое в отдельной строке.

Формат выходных данных
Запишите в ответе два числа: сначала наибольшего точного показания, а затем целую часть среднего арифметического всех точных показаний.

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

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

Артур Числовский и его массив#50335

Артур Числовский получил на свой день рождения массив из N целых чисел в подарок. Но ему он не понравился. Артур Числовский хочет сделать этот массив красивым. Числовский считает массив A₁, A₂, A₃ ... A_N красивым, если A₁ > A_N. Чтобы сделать его красивым, Артур Числовский может поменять местами любые два числа в массиве. Кроме того, Артур Числовский может выполнять эту операцию любое количество раз над смежными парами целых чисел в массиве A. Найдите количество способов, которыми Артур Числовский может сделать этот массив красивым. Два способа считаются одинаковыми, если итоговый массив после всех обменов имеет одинаковые значения A₁ и A_N.

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

Первая строка ввода содержит целое число N, обозначающее количество элементов в массиве A. Следующая строка ввода содержит N разделенных пробелом целых чисел, обозначающих A₁,A₂,A₃ ... A_N соответственно.

Ограничения

1 ≤ N ≤ 10⁶ 1 ≤ A_i ≤ 10⁶

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

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

Примечание
В приведенном примере общее количество способов равно (5,1),(4,1),(3,1),(2,1),(5,2),(4,2),(3,2),(5,3),(4,3),(5,4). Первое число в приведенной выше паре - A[1], а второе - A[N]. Заметим, что два способа считаются одинаковыми, если A[1] и A[N] в результирующем массиве после обмена совпадают.

Сортировка подсчетом

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

26#50315

Каково назначение функции pivot_table() в Pandas?