Сортировка и последовательности

Давайте разберём решение сложной, но очень интересной задачи. Сначала внимательно читаем условие: Пункт про вывод -1 при отсутствии антиарифметической перестановки может сбить с толку и навести на мысль, что они лишь небольшого размера. И интуитивно так и может показаться, ведь добавление каждого последующего числа уменьшает варианты для продолжения. Однако, это неверно. И антиарифметическая перестановка существует для любого N. И чем больше N, тем их больше (в абсолютном выражении, но не в относительном к общему числу перестановок)...

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

Разберём классический алгоритм, который можно расширить для более сложных на примере решения очередной задачи: В этой задаче требуется просто отсортировать массив (список). Подразумевалось, что массив будет большого размера, и стандартные функции сортировки не будут успевать это сделать за отведённое время. Однако задача на сайте уже много лет, и компьютеры становятся быстрее, поэтому данную задачу можно очень просто решить даже на Python (точнее на PyPy): Здесь мы просто считываем данные в список...

Предлагаю посмотреть, как скучную задачу на циклы можно решить с помощью готовых функций на Python. Читаем условие: По сути мы видим здесь две отдельных задачи, у которых лишь общие входные данные. Это накладывает единственное незначительное ограничение, что при решении одной задачи нельзя менять входные данные. Например, если бы мы первую часть решали с помощью сортировки массива и суммы некоторого его суффикса (ведь именно там находились бы положительные числа). Поэтому давайте сразу считаем входные...

Ещё одно красивое решение задачи на Python, благодаря слайсам. К тому же, это одна из тех задач, где нужно сначала провести небольшое исследование: Простыми словами из математики в этой задаче требуется найти минимальный период. Ограничения на входные данные кажутся довольно большими. Так и есть, если вы захотели перебрать все варианты, и для каждого из них пройтись по массиву и убедиться, что элементы совпадают. Перебор можно сократить, заметив, что барабан сделал целое число оборотов. Ведь тогда...

Последние несколько задач показывали, что Python удобнее С++, но в этой задаче всё наоборот. Давайте посмотрим. Если никакие мысли по поводу решения задачи не приходят в голову, то всегда можно написать самое простое решение и позапускать его на разных входных данных. Часто после такого можно найти закономерности или способы сокращения времени работы. В этой задаче можно было бы написать три вложенных цикла и находить максимум. Можно пойти другим путём. Что было бы, если бы все числа были натуральными? Разумно предположить, что тогда максимальное произведение дали бы три самых больших числа...