Контрольная работа 1. Разбор и авторские решения

1. Двухступенчатые выборы УК в многоэтажке

Условие

В доме $m$ этажей, на каждом живёт по $n$ жильцов. Жильцам нужно выбрать одну из 10 управляющих компаний (УК), занумерованных от 0 до 9.

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

На собрании жилищного кооператива (ЖК) делегаты голосуют так, как решили их этажи, и побеждает УК, набравшая больше всего голосов. При равенстве голосов снова побеждает УК с меньшим номером.

Отдельно определите, какая УК победила бы на прямых выборах: то есть какая УК чаще всего встречается среди всех $m \cdot n$ голосов (при равенстве — снова УК с меньшим номером).

Ввод. В первой строке — два целых числа $m$ и $n$ ($1 \le m, n \le 10^5$, $m \cdot n \le 10^6$). В следующих $m$ строках — по $n$ чисел от 0 до 9 через пробел: за какую УК голосует каждый жилец соответствующего этажа.

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

Подсказка. Хранить все $m \cdot n$ чисел не нужно. Достаточно трёх массивов счётчиков по 10 элементов: счётчики текущего этажа, счётчики голосов делегатов и счётчики всех голосов сразу.

Пример

Ввод:

3 3
9 9 9
1 9 1
1 9 1

Вывод:

1 9

Идея и обоснование

Два голосования считают разные вещи. На прямых выборах учитывается каждый голос жильца, а на двухступенчатых — ровно один голос от каждого этажа. Поэтому нужны три массива по 10 счётчиков:

• row[u] — голоса за УК u на текущем этаже;
• total[u] — голоса за неё во всём доме;
• delegates[u] — число этажей, выбравших её своим представителем.

Прочитав этаж, находим победителя по row и увеличиваем соответствующий счётчик delegates на один, независимо от числа голосов на этаже. После всех этажей отдельно выбираем победителей по delegates и total.

Функция best перебирает номера от 0 до 9 и меняет победителя только при строго большем числе голосов. Поэтому при равенстве сохраняется меньший номер: он был рассмотрен раньше. После каждого шага winner — правильный победитель среди уже рассмотренных УК.

В примере этажи выбирают 9, 1, 1, поэтому двухступенчатые выборы выигрывает УК 1. При этом среди всех жильцов за УК 9 проголосовали пятеро, а за УК 1 — четверо: прямые выборы выигрывает УК 9.

Сложность. Подсчёт голосов занимает $O(mn)$, выбор победителей — $O(10m + 10)$, итого $O(mn)$ при $n \ge 1$. Сами счётчики занимают $O(1)$ памяти. Приведённый код читает строку этажа целиком, поэтому с учётом буфера ввода дополнительная память — $O(n)$; весь дом в памяти не хранится.

Граничные случаи и ошибки. Правило ничьей нужно применять на обоих этапах и на прямых выборах. Нельзя заменять голос делегата количеством голосов за победившую на этаже УК. Один этаж или один жилец на этаже не требуют отдельной ветки.

Авторское решение

def best(counter):
    """Номер УК с наибольшим числом голосов; при равенстве — с меньшим номером."""
    winner = 0
    for u in range(1, 10):
        if counter[u] > counter[winner]:
            winner = u
    return winner


m, n = map(int, input().split())
total = [0] * 10
delegates = [0] * 10

for _ in range(m):
    row = [0] * 10
    votes = list(map(int, input().split()))
    for u in votes:
        row[u] += 1
        total[u] += 1
    delegates[best(row)] += 1

print(best(delegates), best(total))

2. Крестьянское умножение

Условие

Дано $q$ запросов. В каждом запросе заданы два неотрицательных целых числа $a$ и $b$. Для каждого запроса вычислите произведение $a \cdot b$ и количество отмеченных строк крестьянского алгоритма, описанного ниже.

Как выполняется умножение

Крестьянский метод не требует таблицы умножения — только деление на 2 и удвоение.

Выпишем две колонки: в первой стоит первый множитель, во второй — второй. На каждом шаге первое число делим на 2 нацело (остаток отбрасываем), а второе удваиваем. Строки выписываем, пока первое число больше нуля, поэтому последняя строка всегда содержит 1 (если $a = 0$, строк нет вовсе). Строку помечаем отметкой, если первое число в ней нечётное. Произведение равно сумме вторых чисел отмеченных строк.

Пример: $45 \cdot 24$.

Отмечены строки с нечётными первыми числами: $24 + 96 + 192 + 768 = 1080$, отмеченных строк — 4.

Тот же процесс коротко записывается так:

Здесь $M(a, b)$ — искомое произведение. Запись $2b$ означает удвоение: в коде его делают сложением (b + b) или сдвигом (b << 1), а не умножением.

Количество отмеченных строк определяется только первым множителем $a$. На 2 всегда делим именно его.

В этой задаче запрещено использовать умножение (*, **, math.prod, operator.mul и любые другие способы перемножить два числа одним действием). Разрешены +, -, //, %, <<, >> и сравнения. Код сдачи смотрит преподаватель: решение с умножением не будет засчитано, даже если тесты пройдены.

Каждый запрос обрабатывается за $O(\log a)$ шагов: при $a = 10^{18}$ их не больше 60.

Ввод. В первой строке — количество запросов $q$ ($1 \le q \le 10^5$). В следующих $q$ строках — по два целых числа $a$ и $b$ ($0 \le a, b \le 10^{18}$).

Вывод. Для каждого запроса — в отдельной строке два числа через пробел: произведение $a \cdot b$ и количество отмеченных строк.

Пример

Ввод:

3
45 24
3 5
0 7

Вывод:

1080 4
15 2
0 0

Идея и обоснование

Поддерживаем сумму total и число отмеченных строк marked. Пока первый множитель положителен, проверяем его нечётность. Если он нечётный, прибавляем текущий второй множитель к сумме и увеличиваем счётчик. После этого делим первый множитель пополам, а второй удваиваем.

В коде a & 1 проверяет младший двоичный разряд, a >>= 1 выполняет целочисленное деление неотрицательного числа на 2, b <<= 1 удваивает число. Умножение при этом не используется.

Пусть исходные множители — $A$ и $B$. Инвариант цикла:

$$ \texttt{total} + a\cdot b = A\cdot B. $$

Если $a=2t$, после перехода остаток произведения равен $t\cdot(2b)=a\cdot b$. Если $a=2t+1$, мы сначала прибавляем $b$ к total, а остаток становится $t\cdot(2b)$; сумма снова сохраняется. При $a=0$ остаток равен нулю, поэтому total содержит исходное произведение.

Счётчик увеличивается ровно в нечётных строках. Иначе это можно понимать как число единиц в двоичной записи исходного первого множителя: деление на 2 последовательно удаляет младшие разряды.

Сложность. При $a>0$ цикл делает $\lfloor\log_2 a\rfloor+1$ итераций, при $a=0$ — ни одной. На один запрос требуется $O(1+\log(a+1))$ времени и $O(1)$ рабочих чисел; при $a\le 10^{18}$ итераций не больше 60. Запросы читаются и обрабатываются по одному, ответы сразу выводятся, поэтому вся программа использует $O(1)$ дополнительной памяти при заданных ограничениях на числа.

Граничные случаи и ошибки. При a = 0 ответ — 0 0. При b = 0 произведение равно нулю, но отмеченные строки всё равно нужно считать: например, для 6 0 ответ — 0 2. Переставлять множители ради меньшего числа шагов нельзя: это может изменить второй компонент ответа. Произведение может достигать $10^{36}$; целые числа Python его вмещают.

Авторское решение

def peasant(a, b):
    """Крестьянское умножение: (a * b, число отмеченных строк).

    Умножение не используется: только сравнение, сдвиги и сложение.
    Первый множитель делим на 2, второй удваиваем; нечётный первый
    множитель отмечает строку. Всего O(log a) шагов.
    """
    total = 0
    marked = 0
    while a:
        if a & 1:
            total += b
            marked += 1
        a >>= 1
        b <<= 1
    return total, marked


def solve(queries):
    return [peasant(a, b) for a, b in queries]


q = int(input())
for _ in range(q):
    a, b = map(int, input().split())
    total, marked = peasant(a, b)
    print(total, marked)

3. Произведение всех, кроме текущего

Условие

Дан массив $a$ из $n$ целых чисел. Постройте массив $b$ той же длины, в котором $b_i$ — произведение всех элементов $a$, кроме $a_i$.

Использовать операцию деления нельзя — код сдачи смотрит преподаватель. Алгоритм должен работать за $O(n)$.

Гарантируется, что при любом $k$ произведение первых $k$ элементов массива и произведение последних $k$ элементов, а также каждый элемент ответа по абсолютной величине не превосходят $10^{18}$. В частности, $|a_i| \le 10^{18}$.

Ввод. В первой строке — целое число $n$ ($2 \le n \le 2 \cdot 10^5$). Во второй строке — $n$ целых чисел $a_i$ через пробел.

Вывод. Одна строка: $n$ чисел $b_i$ через пробел.

Пример

Ввод:

4
1 2 3 4

Вывод:

24 12 8 6

Идея и обоснование

Разобьём произведение всех элементов, кроме текущего, на две независимые части:

$$ b_i = \left(\prod_{j<i} a_j\right)\left(\prod_{j>i} a_j\right). $$

Пустое произведение равно 1: слева от первого элемента и справа от последнего множителей нет.

Создадим два массива длины n + 1:

• prefixes[k] — произведение первых k элементов, то есть элементов полуинтервала [0, k);
• suffixes[k] — произведение последних k элементов, то есть элементов полуинтервала [n - k, n).

Начальные значения prefixes[0] и suffixes[0] равны 1. В одном цикле строим оба массива: к префиксу добавляем очередной элемент слева, к суффиксу — очередной элемент справа.

Для позиции i слева находится i элементов, а справа — n - i - 1. Поэтому ответ равен prefixes[i] * suffixes[n - i - 1]. Эти части вместе содержат все элементы, кроме a[i].

Например, для 1 2 3 4 получаем prefixes = [1, 1, 2, 6, 24] и suffixes = [1, 4, 12, 24, 24]. Ответ на позиции 1 равен prefixes[1] * suffixes[2] = 1 * 12 = 12. Полный ответ — 24 12 8 6.

Сложность. Построение массивов и вывод ответа занимают $O(n)$ времени. Два вспомогательных массива занимают $O(n)$ дополнительной памяти. Отдельный массив ответа не нужен: элементы выводятся сразу.

Граничные случаи и ошибки. Нули и отрицательные числа обрабатываются тем же алгоритмом. При одном нуле ненулевым может быть только ответ на его позиции; при двух и более нулях весь ответ нулевой. Вычислить общее произведение и разделить на a[i] нельзя: деление запрещено, а при нуле такой подход ещё и некорректен. В suffixes индекс означает количество элементов справа, поэтому нужен индекс n - i - 1.

Авторское решение

n = int(input())
a = [int(x) for x in input().split()]

prefixes = [1] * (n + 1)
suffixes = [1] * (n + 1)

for i in range(n):
    prefixes[i + 1] = prefixes[i] * a[i]
    suffixes[i + 1] = suffixes[i] * a[n - i - 1]

for i in range(n):
    print(prefixes[i] * suffixes[n - i - 1], end=' ')

4. Сортировка чисел в разных системах счисления

Условие

В строке через пробел даны $n$ чисел в трёх системах счисления: двоичной (0b…), восьмеричной (0o…) и шестнадцатеричной (0x…). Все числа записаны канонически — так, как их печатают функции bin, oct и hex: префиксы строчными буквами, шестнадцатеричные цифры тоже строчные, ведущих нулей нет.

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

Ввод. В первой строке — целое число $n$ ($1 \le n \le 3000$). Во второй строке — $n$ чисел через один пробел; каждое начинается с 0b, 0o или 0x.

Вывод. Одна строка: те же $n$ чисел через один пробел, каждое на своей позиции и в той же записи, что и во входе.

Разрешены три уровня решения: с дополнительной памятью $O(n)$, in-place сортировкой выбором или in-place быстрой сортировкой с разбиением Ломуто. Все три дают одинаковые баллы.

Пример

Ввод:

7
0b1111 0o7140562 0xa 0b10000 0o12 0xfa6eb1d62c 0b101

Вывод:

0b101 0o7140562 0xfa6eb1d62c 0b1111 0o12 0xa 0b10000

Идея и обоснование

Сортировать весь массив нельзя: позиции классов должны сохраниться, а восьмеричные числа вообще не двигаются. Рассматриваем отдельно подпоследовательность двоичных чисел и подпоследовательность шестнадцатеричных. Сравниваем числовые значения, для чего подходит int(token, 0): основание определяется по префиксу.

Строковая сортировка не подходит. Например, 0b10000 обозначает 16, а 0b101 — 5, хотя лексикографически первая строка меньше второй.

Уровень 1: дополнительные массивы. Собрать двоичные строки в отдельный список, отсортировать по key=lambda token: int(token, 0); шестнадцатеричные отсортировать так же с reverse=True. Затем пройти исходный массив: на каждом двоичном месте взять следующий элемент первого списка, на каждом шестнадцатеричном — второго, восьмеричные оставить. Время $O(n\log(n+1))$, дополнительная память $O(n)$.

Уровень 2: сортировка выбором. Именно этот вариант реализован в авторском коде ниже. Находим очередную позицию нужного класса. Среди всех следующих элементов этого же класса выбираем минимум для двоичных или максимум для шестнадцатеричных и меняем его с текущим элементом. Чужие классы пропускаем.

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

Уровень 3: быстрая сортировка. Можно выполнять разбиение Ломуто только по позициям нужного класса: чужие позиции пропускать и не включать в обмены. Опорный элемент тоже должен принадлежать этому классу. Случайный опорный защищает от систематически неудачных разбиений на отсортированных данных; для большого числа одинаковых значений обычное двухчастное разбиение всё равно может давать квадрат. Стоимость зависит и от проходов через чужие позиции; стандартную оценку сортировки плотного массива нельзя переносить без учёта этих проходов. Рекурсивный стек также считается дополнительной памятью.

Сложность авторского решения. Каждый запуск сортировки выбором занимает $O(n^2)$ времени в худшем случае и $O(1)$ дополнительной памяти сверх массива строк. Сам массив и прочитанный ввод занимают $O(n)$ элементов. Эти оценки считают преобразование и сравнение одного числа элементарными операциями; для строк произвольной длины нужно дополнительно учитывать длину записи.

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

Авторское решение

def sort_class(a, prefix, desc):
    """Сортировка выбором по подпоследовательности (уровень 2 из условия).

    Элементы чужого класса пропускаются и остаются на местах: меняются
    местами только элементы одного класса. Дополнительная память O(1).

    Уровень 3 — то же самое, но с разбиением Ломуто и случайным опорным
    элементом: на уже отсортированном классе опорный «последний элемент»
    даёт глубину рекурсии порядка числа элементов класса.
    """
    n = len(a)
    i = 0
    while True:
        while i < n and not a[i].startswith(prefix):
            i += 1
        if i >= n:
            return

        best = i
        best_val = int(a[i], 0)
        j = i + 1
        while j < n:
            if a[j].startswith(prefix):
                v = int(a[j], 0)
                if (v > best_val) if desc else (v < best_val):
                    best, best_val = j, v
            j += 1

        if best != i:
            a[i], a[best] = a[best], a[i]
        i += 1


n = int(input())
a = input().split()

sort_class(a, "0b", False)  # двоичные — по возрастанию
sort_class(a, "0x", True)   # шестнадцатеричные — по убыванию
print(*a)

5. Поиск в циклически сдвинутом массиве

Условие

Дан массив из $n$ различных целых чисел. Изначально он был отсортирован по возрастанию, после чего его циклически сдвинули — влево или вправо — на неизвестное число позиций. Сдвиг мог быть нулевым.

Для каждого из $q$ запросов найдите индекс элемента, равного $x$. Если такого элемента нет, выведите -1.

После чтения массива каждый запрос должен обрабатываться за $O(\log n)$; полное время работы — $O(n + q \log n)$.

Ввод. В первой строке — целое число $n$ ($1 \le n \le 10^5$). Во второй строке — $n$ различных целых чисел $a_i$ ($-10^9 \le a_i \le 10^9$) через пробел. В третьей строке — количество запросов $q$ ($1 \le q \le 10^5$). В следующих $q$ строках — по одному целому числу $x$ ($-10^9 \le x \le 10^9$).

Вывод. Для каждого запроса — в отдельной строке индекс искомого элемента (нумерация с нуля) или -1, если элемента нет.

Пример

Ввод:

7
4 5 6 7 0 1 2
3
0
3
4

Вывод:

4
-1
0

Идея и обоснование

Сначала найдём индекс минимального элемента pivot. Если мысленно читать массив начиная с него и после конца возвращаться к началу, получим обычный возрастающий массив. Его не нужно создавать: виртуальному индексу j соответствует настоящий индекс

$$ (j + \texttt{pivot})\bmod n. $$

Как найти минимум. До точки сдвига все значения больше последнего элемента a[-1], а начиная с неё — не больше. Поэтому ищем первую позицию, где a[mid] <= a[-1]. Если сдвига нет, условие выполнено с самого начала.

Поддерживаем полуинтервал [lo, hi), изначально [0, n):

• Если a[mid] > a[-1], искомая граница правее mid: оставляем [mid + 1, hi).
• Иначе первая подходящая позиция не правее mid: присваиваем hi = mid и продолжаем поиск в [lo, mid). Сам mid сохраняется как возможный ответ на правой границе.

При lo == hi найдена первая подходящая позиция — индекс минимума. Она всегда существует, поскольку последний элемент удовлетворяет условию. Различность элементов делает разделение на две части однозначным.

Как отвечать на запрос. Делаем обычный бинарный поиск по полуинтервалу виртуальных индексов [0, n), а значение в середине берём из a[(mid + pivot) % n]. Если оно меньше искомого, оставляем [mid + 1, hi); если больше — [lo, mid). Виртуальный массив отсортирован, поэтому стандартное отсечение половины корректно. Когда значение найдено, возвращаем настоящий индекс; если полуинтервал стал пустым — -1.

В примере pivot = 4, виртуально массив имеет вид 0 1 2 4 5 6 7. Виртуальный индекс нуля — 0, но во входном массиве его индекс — 4.

Сложность. Минимум ищется один раз за $O(\log(n+1))$, каждый запрос — за $O(\log(n+1))$. Вместе с чтением ввода получаем $O(n+q\log(n+1))$, что при $n\ge2$ записывают как $O(n+q\log n)$. Бинарные поиски используют $O(1)$ рабочей памяти; массив, запросы и ответы в авторской программе занимают $O(n+q)$.

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

Авторское решение

def find_pivot(a):
    """Индекс минимума в циклически сдвинутом возрастающем массиве."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] > a[-1]:
            lo = mid + 1
        else:
            hi = mid
    return lo


def solve(a, targets):
    """Для каждого target — его индекс (с нуля) или -1.

    Сначала за O(log n) находим точку сдвига, затем для каждого запроса
    делаем обычный бинпоиск по «развёрнутому» индексу: mid + pivot по модулю n.
    Итого O(n + q log n).
    """
    n = len(a)
    pivot = find_pivot(a)
    res = []

    for t in targets:
        lo, hi = 0, n
        found = -1
        while lo < hi:
            mid = (lo + hi) // 2
            real = (mid + pivot) % n
            v = a[real]
            if v == t:
                found = real
                break
            if v < t:
                lo = mid + 1
            else:
                hi = mid
        res.append(found)

    return res


n = int(input())
a = list(map(int, input().split()))
q = int(input())
targets = []
for _ in range(q):
    targets.append(int(input()))

for index in solve(a, targets):
    print(index)

6. Тройки с нулевой суммой

Условие

Дан массив из $n$ целых чисел; числа могут повторяться. Найдите все различные тройки значений $(x, y, z)$, для которых $x + y + z = 0$. Значения тройки берутся с трёх разных позиций массива.

Тройки считаются одинаковыми, если совпадают все три значения; каждую различную тройку нужно вывести ровно один раз.

Ввод. В первой строке — целое число $n$ ($3 \le n \le 3000$). Во второй строке — $n$ целых чисел $a_i$ ($-10^5 \le a_i \le 10^5$) через пробел.

Вывод. Если подходящие тройки есть — в первой строке их количество $k$, затем $k$ строк по три числа через пробел. Внутри каждой тройки числа идут по неубыванию, сами тройки — в лексикографическом порядке. Если подходящих троек нет — одна строка с числом 0.

Пример

Ввод:

6
-1 0 1 2 -1 -4

Вывод:

2
-1 -1 2
-1 0 1

Идея и обоснование

Сортируем массив. Фиксируем индекс i первого элемента тройки, а оставшиеся два ищем на полуинтервале [lo, hi), изначально [i + 1, n). Берём его крайние элементы a[lo] и a[hi - 1]. Продолжаем, пока lo + 1 < hi: тогда i < lo < hi - 1, поэтому используются три разные позиции.

Обозначим сумму текущей тройки через s.

• Если s < 0, увеличиваем lo. Даже с наибольшим доступным третьим элементом сумма слишком мала, поэтому для текущего lo решения нет.
• Если s > 0, уменьшаем hi. Даже с наименьшим доступным вторым элементом сумма слишком велика, поэтому для текущего hi решения нет.
• Если s == 0, сохраняем тройку, сдвигаем оба указателя и пропускаем повторения найденных второго и третьего значений.

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

Чтобы не получать одну тройку при разных одинаковых первых элементах, пропускаем a[i], если оно равно предыдущему. При a[i] > 0 перебор можно закончить: все оставшиеся элементы положительны.

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

Сложность. Сортировка занимает $O(n\log n)$. Для каждого i указатели суммарно делают $O(n)$ шагов, всего $O(n^2)$. Если найдено $K$ троек, их хранение и вывод требуют $O(K)$ памяти; вместе с сортировкой Python и входными данными память программы — $O(n+K)$, в худшем случае $O(n^2)$.

Граничные случаи и ошибки. Для 0 0 0 0 выводится одна тройка 0 0 0. Тройку -1 -1 2 можно использовать только при наличии двух минус единиц. Удалять все повторы из массива перед поиском нельзя: это уничтожит такие решения. В первой строке вывода обязательно должно быть количество троек, включая 0, если ответ пуст.

Авторское решение

def solve(a):
    """Все различные тройки с нулевой суммой, в лексикографическом порядке.

    Сортируем массив; для каждого кандидата в первый элемент тройки идём
    двумя указателями с концов остатка. Тройки получаются уже
    лексикографически упорядоченными, а повторы отсекаются пропуском
    одинаковых соседей. O(n^2) времени.
    """
    a.sort()
    n = len(a)
    triples = []

    for i in range(n - 2):
        if a[i] > 0:
            break                       # дальше все числа положительны
        if i > 0 and a[i] == a[i - 1]:
            continue                    # такой первый элемент уже разбирали

        lo, hi = i + 1, n
        while lo + 1 < hi:
            s = a[i] + a[lo] + a[hi - 1]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                triples.append((a[i], a[lo], a[hi - 1]))
                lo += 1
                hi -= 1
                while lo + 1 < hi and a[lo] == a[lo - 1]:
                    lo += 1
                while lo + 1 < hi and a[hi - 1] == a[hi]:
                    hi -= 1

    return triples


n = int(input())
a = list(map(int, input().split()))
triples = solve(a)
print(len(triples))
for x, y, z in triples:
    print(x, y, z)

7. Общий привал

Условие

Туристическая группа растянулась вдоль прямой тропы. Тропа размечена столбиками с целыми номерами: турист номер $i$ стоит у столбика $x_i$ и устаёт на $w_i$ за каждый пройденный километр — в любую сторону.

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

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

Ввод. В первой строке — число туристов $n$ ($1 \le n \le 10^4$). В каждой из следующих $n$ строк — два целых числа $x_i$ и $w_i$ через пробел: у какого столбика стоит турист и насколько он устаёт за километр ($-10^9 \le x_i \le 10^9$, $1 \le w_i \le 10^4$). Туристы перечислены в произвольном порядке.

Вывод. Одно целое число — наименьшая суммарная усталость.

Пример

Ввод:

3
1 2
3 1
8 4

Вывод:

19

Идея и обоснование

Для места привала $t$ суммарная усталость равна

$$ F(t)=\sum_{i=1}^{n}w_i|x_i-t|. $$

Без весов минимум достигается в обычной медиане. Здесь каждый турист влияет на ответ с весом $w_i$, поэтому нужна взвешенная медиана.

Сортируем пары (x, w) по координате. Пусть $W=\sum_i w_i$ — общий вес. Берём первую координату, на которой накопленный вес достигает

$$ \left\lceil\frac W2\right\rceil =\left\lfloor\frac{W+1}{2}\right\rfloor. $$

Это и есть координата best_x в коде. После её нахождения одним проходом считаем $F(\texttt{best_x})$.

Почему это минимум. При сдвиге места привала с целого $t$ на $t+1$ туристы с $x_i\le t$ идут на километр больше, а туристы с $x_i\ge t+1$ — на километр меньше. Других случаев нет, поскольку координаты целые. Поэтому

$$ F(t+1)-F(t)=\sum_{x_i\le t}w_i-\sum_{x_i\ge t+1}w_i. $$

Эта разность не убывает при движении вправо. До выбранной координаты накопленный вес меньше половины, поэтому сдвиг вправо уменьшает усталость. Начиная с выбранной координаты вес слева, включая её, не меньше половины, поэтому дальше вправо улучшения нет. Значит, выбранная координата минимизирует $F$.

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

В примере общий вес равен 7, порог — 4. Накопленные веса на координатах 1, 3, 8 равны 2, 3, 7, поэтому берём 8. Ответ: $2\cdot7+1\cdot5+4\cdot0=19$.

Сложность. Сортировка — $O(n\log(n+1))$, остальные проходы — $O(n)$. Память — $O(n)$ для списка туристов и его отсортированной копии.

Граничные случаи и ошибки. При одном туристе или совпадении всех координат ответ нулевой. Отрицательные координаты обрабатываются обычным модулем разности. Обычная медиана игнорирует веса, а среднее не минимизирует сумму модулей: например, для (0, 1) и (10, 100) оптимум — 10, а не 0 или 5. Перебор всех целых координат слишком дорог из-за диапазона до $2\cdot10^9$.

Авторское решение

def solve(tourists):
    """Минимум суммы w_i * |x_i - x| по целому x.

    Минимум достигается во взвешенной медиане: берём первое x, для которого
    накопленный вес достигает половины общего. Любая взвешенная медиана даёт
    одно и то же значение. Сложность O(n log n).
    """
    pts = sorted(tourists)
    total_w = sum(w for _, w in pts)
    need = (total_w + 1) // 2

    acc = 0
    best_x = pts[-1][0]
    for x, w in pts:
        acc += w
        if acc >= need:
            best_x = x
            break

    return sum(w * abs(x - best_x) for x, w in pts)


n = int(input())
tourists = []
for _ in range(n):
    x, w = map(int, input().split())
    tourists.append((x, w))
print(solve(tourists))

8. Вышки вдоль трассы

Условие

Вдоль прямой трассы стоят $n$ посёлков, пронумерованных от 1 до $n$ по порядку. В $i$-м посёлке уже установлено $s_i$ вышек связи. Каждая вышка достаёт до посёлков, номера которых отличаются от номера её посёлка не больше чем на $r$: вышка в посёлке $j$ покрывает посёлки с $j - r$ по $j + r$ — те из них, что есть на трассе.

Качество связи в посёлке — это число вышек, которые его покрывают. Связь на трассе хороша настолько, насколько она хороша в самом плохом посёлке.

Оператор может поставить ещё не больше $k$ вышек: в любые посёлки, в один посёлок можно и несколько. Новая вышка покрывает посёлки ровно так же, как уже стоящие. Какого наибольшего качества связи в самом плохом посёлке можно добиться?

Ввод. В первой строке — три целых числа $n$, $r$ и $k$ через пробел ($1 \le n \le 3 \cdot 10^4$, $0 \le r < n$, $0 \le k \le 10^9$). Во второй строке — $n$ целых чисел $s_i$ через пробел ($0 \le s_i \le 10^5$).

Вывод. Одно целое число — наибольшее возможное качество связи в самом плохом посёлке.

Пример

Ввод:

6 1 3
2 0 1 0 0 3

Вывод:

3

Идея

Вместо прямого поиска оптимального размещения решим задачу проверки: можно ли добиться качества хотя бы $M$ в каждом посёлке, добавив не больше $k$ вышек?

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

Исходное покрытие за линейное время

В коде посёлки нумеруются с нуля. Каждая из s[j] вышек посёлка j прибавляет единицу на полуинтервале

$$ [\max(0,j-r),\ \min(n,j+r+1)). $$

Добавляем s[j] на весь этот полуинтервал через разностный массив: плюс в lo, минус в hi. Правая граница hi в покрытие уже не входит. Один проход префиксной суммой восстанавливает cov[i] — исходное качество в каждом посёлке. Так подготовка занимает $O(n)$, независимо от радиуса.

Жадная проверка

Идём слева направо. Пусть added — число ранее добавленных вышек, которые ещё покрывают текущий посёлок i. Если cov[i] + added < M, не хватает

$$ \texttt{need}=M-\texttt{cov[i]}-\texttt{added} $$

вышек. Ставим ровно столько в самый правый посёлок, откуда они ещё покрывают i:

$$ j=\min(n-1,i+r). $$

Сразу увеличиваем added. На ещё не обработанные посёлки эти вышки влияют на полуинтервале [i, min(n, j + r + 1)): записываем отрицательное событие на его правой границе hi. В начале каждой итерации применяем событие текущей позиции, чтобы вычесть вышки, которые уже не достают до неё.

Число новых вышек считаем отдельно в total. Если оно превысило $k$, проверка немедленно возвращает False; если все посёлки обработаны — True. Каждая проверка создаёт свой разностный массив: размещения для разных $M$ независимы.

Почему жадный выбор корректен

Когда дошли до i, посёлки левее уже обеспечены качеством $M$ установленными на предыдущих шагах вышками. Если текущему посёлку не хватает need, любое продолжение обязано добавить хотя бы need вышек, покрывающих i.

Любую такую новую вышку можно перенести в j = min(n - 1, i + r). Она продолжит покрывать i и не потеряет ни одного покрываемого ею посёлка правее i: её правый конец покрытия сдвинется вправо, а левый останется не правее i. Потеря её покрытия слева от i не мешает, потому что эти посёлки уже обеспечены предыдущими жадными установками.

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

Бинарный поиск и сложность

Исходный минимум min(cov) уже достижим. В посёлке, где он достигается, каждая новая вышка улучшает качество не более чем на один, поэтому ответ не превосходит min(cov) + k.

Ищем первое недостижимое значение на полуинтервале [0, min(cov) + k + 1). Правая граница заведомо недостижима и служит ответом, если внутри полуинтервала недостижимых значений нет. Середина — (lo + hi) // 2. Если она достижима, оставляем [mid + 1, hi); иначе запоминаем её как возможную границу и продолжаем в [lo, mid), присвоив hi = mid. При lo == hi найдено первое недостижимое значение, поэтому максимальное достижимое равно lo - 1.

Подготовка и одна проверка занимают $O(n)$, память — $O(n)$. Обозначив $U=\min(\texttt{cov})+k$, получаем время авторской программы $O(n(1+\log(U+1)))$. Если начать поиск с lo = min(cov), оценка улучшается до $O(n(1+\log(k+1)))$, поскольку ширина диапазона равна $k$. При данных ограничениях оба варианта быстрые.

Граничные случаи и ошибки. При k = 0 ответ — исходный минимум. При r = 0 каждая вышка помогает только своему посёлку. При r = n - 1 каждая вышка покрывает всю трассу и ответ равен sum(s) + k. Новые вышки лучше ставить как можно правее, а не обязательно в текущий посёлок. Событие окончания покрытия ставится после последнего покрытого посёлка; ошибка на единицу меняет ответ.

Авторское решение

def coverage(n, r, s):
    """Сколько вышек покрывает каждый посёлок с учётом радиуса r."""
    diff = [0] * (n + 1)
    for j in range(n):
        lo = j - r
        if lo < 0:
            lo = 0
        hi = min(n, j + r + 1)
        diff[lo] += s[j]
        diff[hi] -= s[j]

    cov = [0] * n
    cur = 0
    for i in range(n):
        cur += diff[i]
        cov[i] = cur
    return cov


def feasible(n, r, k, cov, m):
    """Можно ли не более чем k вышками сделать качество не меньше m.

    Идём слева направо. В первом посёлке, где качества не хватает, ставим
    недостающие вышки как можно правее (в i + r): так они покроют максимум
    следующих посёлков. Жадность оптимальна: посёлки левее уже удовлетворены,
    а сдвиг вышек вправо их не портит.
    """
    added = 0
    total = 0
    diff = [0] * (n + 1)

    for i in range(n):
        added += diff[i]
        need = m - cov[i] - added
        if need > 0:
            total += need
            if total > k:
                return False
            j = i + r
            if j > n - 1:
                j = n - 1
            hi = min(n, j + r + 1)
            added += need
            diff[hi] -= need

    return True


def solve(n, r, k, s):
    cov = coverage(n, r, s)

    # качество посёлка не больше cov[i] + k, значит ответ не больше min(cov) + k
    lo = 0
    hi = min(cov) + k + 1
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(n, r, k, cov, mid):
            lo = mid + 1
        else:
            hi = mid
    return lo - 1


n, r, k = map(int, input().split())
s = list(map(int, input().split()))
print(solve(n, r, k, s))