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

Контрольное значение - 4#50887

Профессор Селезнев передает Алисе зашифрованную информацию, которая представляет собой последовательность целых чисел. Все числа данной последовательности не превышают 10⁷. Каждое число передается в течении одной секунды. Чтобы понять, что данные переданы правильно, Алисе необходимо определить контрольное значение, которое вычисляется по следующему правилу,
- берутся три переданных значения из последовательности таким образом, чтобы между между какими-либо двумя соседними моментами передачи прошло ровно K секунд (между передачей первого выбранного числа и второго или между передачей второго выбранного числа и третьего);
- вычисляется сумма выбранных чисел, которая должна быть минимальной. Данная сумма является контрольным значением.
Помогите Алисе определить контрольное значение.

Формат входных данных
В первой строке записано количество чисел N (1 ≤ N ≤ 2·10⁵) и целое число K (1 ≤ K < 10⁵, K < N). Каждая из следующих N строк содержит одно целое число, по модулю не превышающее 10⁷.

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

Линейные алгоритмы Префиксные суммы(минимумы, ...)

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

generate_type_1_2#50871

Определите, сколько раз выполнится тело цикла, а также последнее число, которое будет выведено на экран в процессе выполнения программы. В ответе запишите два числа через пробел: сначала сколько раз выполнится цикл, затем последнее выведенное число. Если программа ничего не выводит на экран, то в вместо второго числа напишите слово None.

n = {1}
while n >= {2}:
    print(n)
    n = n - {3}

Цикл while

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

generate_type_1_1#50867

n = {1}
while n < {2}:
    print(n)
    n = n + {3}

Цикл while

1 100труднаяВойти и решать

Самокат#50864

В городе Новый Нижгород открылась новая служба доставки еды с оригинальным названием <<Камосат>>. Курьеры этой службы передвигаются на самокатах и стремятся максимально эффективно доставлять заказы клиентам.

Для того чтобы упростить задачу планирования маршрутов, был разработан алгоритм, основанный на топографии города. Город расположен вдоль реки, поэтому его можно представить одномерным массивом, где каждый элемент массива — это высота местности в соответствующей точке. Расстояние между двумя соседними точками считается равным \(1\).

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

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

Формат входных данных
Первая строка содержит одно целое число \(n\) (\(2 \leq n \leq 300\,000\)) — количество точек в городе.

Вторая строка содержит \(n\) целых чисел \(h_1, h_2, \ldots, h_n\) (\(-10^9 \leq h_i \leq 10^9\)) — высоты точек города.

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

Замечание

В первом примере курьер может стартовать в третьей точке с высотой \(6\) и проехать по высотам \(6\rightarrow2\rightarrow1\).

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

В третьем примере курьер может проехать по высотам \(5\rightarrow2\rightarrow3\rightarrow4\).

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

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

Урок физкультуры#50863

В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на <<первый–\(k\)-й>>.

Как известно, расчёт на <<первый–\(k\)-й>> происходит следующим образом: первые \(k\) человек имеют номера \(1, 2, 3, \ldots, k\), следующие \(k - 1\) человек имеют номера \(k - 1, k - 2, \ldots, 1\), следующие \(k - 1\) человек имеют номера \(2, 3, \ldots, k\) и т.д. Таким образом, расчёт повторяется через каждые \(2k - 2\) позиции. Примеры расчёта приведены в разделе <<Замечание>>.

Мальчик Вася постоянно всё забывает. Например, он забыл позицию, которую занимал в шеренге. Но он помнит число \(k\), описанное выше, номер, который он получил при расчёте, а также, что его позиция в шеренге была не больше \(n\). Другими словами, если Вася стоял на позиции \(y\) в шеренге, то \(y \leq n\). Помогите Васе понять, сколько есть различных позиций в ряду, где он мог стоять.

Формат входных данных
Первая строка содержит одно целое число \(k\) (\(2 \leq k \leq 10^9\)) — характеристика расчёта, описанная в условии.

Вторая строка содержит одно целое число \(x\) (\(1 \leq x \leq k\)) — номер, который Вася получил при расчёте.

Третья строка содержит одно целое число \(n\) (\(x \leq n \leq 10^9\)) — верхнее ограничение на позицию Васи.

Формат выходных данных
Выведите единственное целое число – количество различных позиций, которые подходят под данные ограничения.

Замечание

В первом примере подходят позиции равные \(2, 4, 6, 8, 10\).

Во втором примере подходят позиции равные \(2, 4, 6, 8, 10\).

В третьем примере подходят позиции равные \(3\) и \(7\).

Пример расчёта для \(k = 2\), \(k = 3\) и \(k = 5\):

k\№	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)	\(10\)
\(2\)	\(1\)	\(2\)	\(1\)	\(2\)	\(1\)	\(2\)	\(1\)	\(2\)	\(1\)	\(2\)
\(3\)	\(1\)	\(2\)	\(3\)	\(2\)	\(1\)	\(2\)	\(3\)	\(2\)	\(1\)	\(2\)
\(5\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(4\)	\(3\)	\(2\)	\(1\)	\(2\)

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

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

Разрез прямоугольника#50862

У Пети есть прямоугольник размера \(a \times b\) с целыми сторонами, хотя бы одна из которых больше \(1\). Он пробует разрезать этот прямоугольник на два прямоугольника с целыми сторонами, сделав разрез, параллельный какой-то из сторон исходного прямоугольника. Затем Петя пытается из двух получившихся прямоугольников сложить какой-то отличный от исходного прямоугольник, при этом он может как угодно поворачивать и двигать эти два прямоугольника. Если у него получается это сделать, то он называет прямоугольник \(a \times b\) интересным.

Обратите внимание, что если два прямоугольника отличаются поворотом на \(90^{\circ}\), то они считаются одинаковыми. Например, прямоугольники \(6 \times 4\) и \(4 \times 6\) считаются одинаковыми.

Таким образом, прямоугольник \(2 \times 6\) является интересным, потому что его можно разрезать на два прямоугольника \(2 \times 3\), после чего из этих двух прямоугольников сложить прямоугольник \(4 \times 3\), который отличается от прямоугольника \(2 \times 6\).

При этом прямоугольник \(2 \times 1\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 1\), а из них можно сложить только прямоугольники \(1 \times 2\) и \(2 \times 1\), которые считаются одинаковыми с исходным.

Также у Пети есть некоторое целое число \(n\). Он хочет узнать, сколько существует различных интересных прямоугольников со сторонами, которые являются целыми числами, не превосходящими \(n\). Помогите ему это сделать.

Формат входных данных
Первая и единственная строка содержит одно целое число \(n\) (\(2 \le n \le 2 \cdot 10^9\)) — ограничение на длину сторон прямоугольника.

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

Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать.

Замечание

В первом примере только прямоугольник \(2 \times 2\) является интересным: его можно разрезать на два прямоугольника \(1 \times 2\), а из них можно сложить прямоугольник \(1 \times 4\). Обратите внимание, что прямоугольник \(1 \times 1\) не является интересным, потому что хотя бы одна сторона должна быть больше \(1\).

Во втором примере прямоугольники \(2 \times 2\) и \(2 \times 3\) являются интересными. Прямоугольник \(2 \times 3\) можно разрезать на два прямоугольника \(1 \times 3\), а из них можно сложить прямоугольник \(1 \times 6\). Прямоугольник \(3 \times 3\) не является интересным, потому что его можно разрезать только на два прямоугольника \(1 \times 3\) и \(2 \times 3\), но из них можно сложить только прямоугольник \(3 \times 3\). Обратите внимание, что прямоугольники \(2 \times 3\) и \(3 \times 2\) считаются одинаковыми, поэтому в ответе их нужно учесть только один раз.

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

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

Число делителей#50691

Задано число \(n\). Требуется найти число от 1 до \(n\), включительно, которое имеет максимальное число положительных целых делителей.

Например, если \(n = 20\), то искомое число — 12, у него 6 делителей: 1, 2, 3, 4, 6 и 12.

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

Формат выходных данных
Выведите на первой строке число от 1 до \(n\), включительно, которое имеет максимальное число делителей. На второй строке выведите число его делителей.

Если есть несколько чисел от 1 до \(n\) с максимальным числом делителей, выведите любое из них.

Алгоритмы обработки Простые числа и разложение на множители

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

Словарь#50553

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

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

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

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

Формат входных данных
В первой строке содержится единственное целое число \(N\) (\(1 \le N \le 100\)) — количество английских слов в словаре. Далее следует \(N\) описаний. В первой строке каждого описания содержится английское слово. В следующей строке записано единственное число \(K \ge 1\) — количество переводов. В следующих \(K\) строках приведены переводы текущего английского слова на латинский, по одному в каждой строке.

Все слова состоят только из маленьких латинских букв. Общее количество слов на входе не превышает \(100\). Длина каждого слова не превосходит 15 символов.

Формат выходных данных
Выведите соответствующий данному латинско-английский словарь в следующем формате. В первую строку запишите единственное целое число \(N\) — количество латинских слов в словаре. Далее выведите \(N\) описаний, каждое описание в отдельной строке: сначала латинское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого латинского слова на английский.

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

Алгоритмы поиска Обработка текста Словари

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

Пицца#50540

Компания из \(M\) человек пришла в пиццерию. Посовещавшись, они решили заказать одну большую пиццу с \(K\) начинками. Пицца представляет собой круг, поделённый на \(K\) равных секторов, в каждом из которых находится своя начинка. Пиццу подают ещё не разрезанной.

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

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

Формат входных данных
Вводятся два целых числа \(K\), \(M\) (\(1 \le K \le 100\), \(1 \le M \le 100\)) — количество начинок в пицце и количество человек в компании соответственно.

Формат выходных данных
Выведите количество человек, которым достанется более одной начинки в наилучшем случае.

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

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

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

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

Стековое кодирование#50452

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

Изначально вам дан пустой стек и пустой массив. Кодом массива \(a\) назовем последовательность действий вида

\(\mathtt{push}(x)\) — положить число \(x\) на вершину стека;
\(\mathtt{pop}\) — снять число с вершины стека;
\(\mathtt{print}\) — выписать в конец массива все элементы стека по порядку от нижнего к верхнему,

приводящую к тому, что в изначально пустой массив оказываются выписаны все элементы \(a\) по порядку. При выполнении третьей операции стек не очищается.

Например, при выполнении последовательности действий \(\mathtt{push}(1)\), \(\mathtt{push}(2)\), \(\mathtt{print}\), \(\mathtt{print}\), \(\mathtt{pop}\) и \(\mathtt{print}\) в массив оказываются выписаны числа \([1, 2, 1, 2, 1]\), а на стеке остается лежать только число \(1\). То есть такая последовательность является кодом массива \([1, 2, 1, 2, 1]\) длины \(6\).

Вам дан массив \(a\) и \(q\) запросов: какой у отрезка массива \(a\) с \(l_i\)-го по \(r_i\)-й элемент включительно минимальный по количеству действий со стеком код?

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

Формат входных данных
В первой строке ввода даны четыре целых числа \(n\) и \(q\) — длина массива \(a\), про отрезки которого спрашивается в запросах, количество запросов, а также максимальный балл за тест и параметр \(\gamma\), указанный в системе оценивания, которые ваше решение может игнорировать \((1 \le n \le 2000\); \(1 \le q \le 10^4\)).

Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\) (\(1 \le a_i \le 10^9\)).

В \(i\)-й из следующих \(q\) строк даны два целых числа \(l_i\) и \(r_i\) — границы отрезка из \(i\)-го запроса (\(1 \le l_i \le r_i \le n\)).

Формат выходных данных
Для каждого запроса выведите в отдельной строке целое число \(k\) от \(1\) до \(n + 1\) — количество действий в вашем коде соответствующего отрезка массива, после чего в следующей строке выведите через пробел \(k\) целых чисел, описывающих эти действия в порядке их выполнения:

для действия \(\mathtt{push}(x)\) выведите число \(x\) от \(1\) до \(10^9\);
для действия \(\mathtt{pop}\) выведите число \(-1\);
для действия \(\mathtt{print}\) выведите число \(0\).

Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива \(a\), ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше \(n + 1\) действия.

Задача на реализацию Задачи на моделирование Стек

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

Смешивание напитков#50451

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

Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито \(n\) сортов, \(i\)-й сорт характеризуется уровнем крепости \(p_i\) и высотой слоя, который он занимает в кружке, \(h_i\). При этом если \(i < j\), то слой кофе \(i\)-го сорта находится ниже кофе \(j\)-го сорта. Также известно, что высота кружки равна \(\sum\limits_{i=1}^n h_i\), то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.

Для разнообразия иногда хочется получить из такого <<коктейля>> напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как \[P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}\]

Чтобы как-то изменять \(P\), можно

выбрать трубочку произвольной высоты \(h\);
один или более раз выполнить следующее: погрузить ее в напиток на любую глубину от \(0\) до \(h\) включительно относительно верхнего края кружки (не относительно текущего уровня жидкости) и отпить произвольное (не обязательно целое) количество кофе с того уровня, на который попал нижний конец трубочки.

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

Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости \(t_i\), и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка \(t_i\).

Формат входных данных
В первой строке ввода даны два целых числа \(n\) и \(q\) — количество слоев кофе в кружке и количество запросов (\(1 \le n, q \le 2 \cdot 10^5\)).

Следующие \(n\) строк содержат по два целых числа \(p_i\) и \(h_i\) — уровень крепости и высоту \(i\)-го снизу кружки слоя кофе (\(1 \le p_i, h_i \le 10^9\)). Гарантируется, что сумма \(p_i \cdot h_i\) по всем \(i\) не превосходит \(10^{18}\).

В \(i\)-й из следующих \(q\) строк дано единственное целое число \(t_i\), определяющее \(i\)-й запрос (\(1 \le t_i \le 10^9\)).

Формат выходных данных
Выведите \(q\) строк, в \(i\)-й из которых содержится единственное целое число от \(0\) до \(n\) — ответ \(i\)-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число \(-1\).

Замечание
Для примера из условия:

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

Бинарный поиск по ответу Вывод формулы Дерево отрезков, RSQ, RMQ

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

Пары, свободные от квадратов#50337

Целое число \(x\) называется свободным от квадратов, если нет такого целого числа \(y > 1\), что \(x\) делится на \(y^2\), то есть \(x = y^2z\) для некоторого целого \(z\).

Даны числа \(l\) и \(r\). Требуется найти число пар целых чисел \((a, b)\), таких что \(l \le a < b \le r\), и числа \(a\), \(b\), а также их произведение \(ab\) свободны от квадратов.

Формат входных данных
На вход подается две строки, первая содержит целое число \(l\), а вторая "— целое число \(r\) (\(1 \le l < r \le 10^9\), \(r - l \le 1000\)).

Формат выходных данных
Выведите одно целое число — искомое число пар.

Примечание
В примере подходят пары \(a = 3, b = 5\), \(a = 5, b = 6\). Число \(4\) не может входить в пару, так как \(4 = 2^2\cdot 1\), а пара \(a = 3, b = 6\) не подходит, так как \(ab = 3\cdot 6 = 18 = 3^2\cdot 2\).

Задача на реализацию Простые числа и разложение на множители

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

20#50314

Что позволяет делать функция groupby() в Pandas?