В этом году главой Флатландии является Егор. Всего...

Ниже приведено разъяснение и один из способов решить задачу (с кодом на Python в конце).

Идея решения

Нам нужно разбить множество из $N$ точек (каждая точка — дом жителя) на как можно большее число троек, причём каждая тройка должна образовывать невырожденный треугольник (то есть точки троих людей не лежат на одной прямой). При этом каждый человек может входить не более чем в одну тройку.

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

Обозначим:

• $N$ — общее число точек.
• $M$ — максимально возможное количество точек, лежащих на одной прямой (размер «самой большой коллинеарной подмножности»).
• $K = N - M$ — число «остальных» точек (то есть точек, не входящих в ту самую большую коллинеарную подмножность).

Ключевой результат

Оказывается, максимальное количество невырожденных троек можно выразить через $N$, $M$ и $K$ следующей простой формулой:

1. Если $M \le 2 \cdot K$, то ответ равен

   $$\left\lfloor \frac{N}{3} \right\rfloor.$$

   Иными словами, если «самая большая прямая» не слишком велика (не более чем в 2 раза больше оставшегося множества), можно «дотянуться» до классического максимума $\lfloor N/3 \rfloor$.

2. Если же $M > 2 \cdot K$, то максимальное число троек равно

   $$K = N - M.$$

   В такой ситуации слишком много точек лежит на одной прямой, и чтобы каждая такая тройка была невырожденной, в ней должно быть не более двух точек с этой «большой» прямой и хотя бы одна точка «снаружи». Но «снаружи» всего $K$ точек, значит и троек мы можем сделать не более $K$.

Также легко проверить «крайние» случаи:

• Если все $N$ точек коллинеарны ($M = N$), тогда $K = 0$, и по формуле получаем $\min\bigl(\lfloor N/3\rfloor,0\bigr) = 0$. Треугольников нет.
• Если $M \le 2(N - M)$ (то есть $M \le 2K$), чаще всего мы и вправду можем достичь $\lfloor N/3\rfloor$.

Как найти $M$

Чтобы применить формулу, нужно уметь находить $M$ — размер наибольшего коллинеарного подмножества. В самых простых вариантах (или при небольшом $N$) это можно делать за $O(N^2)$ следующим образом:

1. Для каждой точки $p_i$ перебираем все остальные точки $p_j$ (j \лон» (или вектор направления) \(\overrightarrow{p_i p_j}. Чтобы не столкнуться с проблемами плавающей точки при вычислении угла или дробного наклона, удобно использовать нормализованные пары целых $(dx, dy)$, где: $$dx = x_j - x_i,\quad dy = y_j - y_i,$$ и затем мы сокращаем $(dx, dy)$ на их $\gcd(dx, dy)$, учитываем знак (например, храним пару так, чтобы $dx \ge 0$, а при $dx=0$ следим за знаком $dy$, и т.д.).
2. Подсчитываем в хэше (словаре) количество точек $p_j$, дающих один и тот же «направляющий» вектор из $p_i$. Максимум по всем направлениям + 1 (считая саму $p_i$) даёт количество точек, коллинеарных вместе с $p_i$, лежащих на одной прямой.
3. Сохраняем глобальный максимум.

Так мы найдём $M$. Если $N$ не слишком велико, $O(N^2)$ вполне допустимо. Если же $N$ очень большое (десятки или сотни тысяч), потребуется более изощрённый метод, но сама формула останется той же.

Итоговый алгоритм

1. Считать $N$.
2. Считать координаты всех точек.
3. Если $N < 3$, то сразу ответ 0 (из менее чем трёх точек невырожденный треугольник не построишь).
4. Найти $M$ — максимальное число точек на одной прямой.
5. Вычислить $K = N - M$.
6. Если $M \le 2K$, вывести $\lfloor N/3 \rfloor$.
7. Иначе вывести $K$.

Ниже приведён пример кода на Python, реализующий эту идею в «простом» $O(N^2)$ стиле (с учётом, что $N$ не слишком большой). В нём показано, как искать $M$, и как затем применять формулу.

python
def solve():
    import sys
    input_data = sys.stdin.read().strip().split()
    # Первый элемент - N, далее идут координаты
    N = int(input_data[0])
    coords = input_data[1:]
    
    # Если меньше 3 - треугольников нет
    if N < 3:
        print(0)
        return
    
    points = []
    idx = 0
    for _ in range(N):
        x = int(coords[idx]); y = int(coords[idx+1])
        idx += 2
        points.append((x, y))
    
    # Функция для вычисления НОД
    from math import gcd
    
    # Если вдруг все точки совпадают (по условию задачи не должны, но на всякий случай):
    # Или если попробуем проверить вдруг - тогда M=N
    # Но условие гарантирует, что все точки различны, так что пропустим проверку на идентичные
    
    # Случай, когда все точки могут оказаться на одной прямой:
    # Проверим это в процессе подсчёта.
    
    # Найдём M: максимальное число точек, лежащих на одной прямой
    M = 1  # Как минимум 1 точка сама с собой :)
    
    for i in range(N):
        x_i, y_i = points[i]
        # Словарь: (dx, dy) -> сколько точек имеют такой вектор из points[i]
        slope_count = {}
        local_max = 0
        
        for j in range(i+1, N):
            x_j, y_j = points[j]
            dx = x_j - x_i
            dy = y_j - y_i
            # Нормализуем (dx, dy):
            if dx == 0:
                # Вертикальная прямая
                dy = 1
            elif dy == 0:
                # Горизонтальная прямая
                dx = 1
            else:
                sign = -1 if (dx*dy < 0) else 1
                dx, dy = abs(dx), abs(dy)
                g = gcd(dx, dy)
                dx //= g
                dy //= g
                dx *= sign
            slope_count[(dx, dy)] = slope_count.get((dx, dy), 0) + 1
            local_max = max(local_max, slope_count[(dx, dy)])
        
        # local_max - это максимум "по направлению" из i-й точки;
        # Но число точек на прямой вместе с i-й точкой = local_max + 1
        M = max(M, local_max + 1)
        
        # Если вдруг M уже достигнет N, дальше смысла считать нет:
        if M == N:
            break
    
    # Теперь у нас есть M. Применяем формулу:
    K = N - M
    
    if M <= 2 * K:
        print(N // 3)
    else:
        print(K)

Пояснения к коду

1. Чтение входных данных:
   • N — количество точек,
   • Далее все координаты следуют подряд.
2. Проверка на $N < 3$: если точек меньше трёх, треугольников быть не может.
3. Поиск M (размер максимальной коллинеарной подмножности):
   • Для каждой точки $i$ вычисляем для всех других $j$ вектор $(dx, dy)$.
   • Нормируем этот вектор (учитываем знак, сокращаем на НОД, отдельно обрабатываем вертикали/горизонтали).
   • Считаем в slope_count, сколько раз встречается тот или иной нормализованный вектор. Максимум по slope_count даёт, сколько точек $j$ лежит на одной прямой с $i$. Прибавив саму точку $i$, получаем число точек на прямой.
   • Глобальный максимум и будет нашим M.
4. Формула:
   • $K = N - M$.
   • Если $M \le 2K$, выводим $\lfloor N/3 \rfloor$. Иначе выводим $K$.

Таким образом, решение будет корректно находить максимально возможное число «счастливых троек» (невырожденных треугольников), в каждую из которых входят ровно 3 человека, причём каждый человек участвует не более чем в одной тройке.

Ниже упрощённое объяснение и код на Python.

––––––––––––––––––––––––––––––––––––––––––
Объяснение
––––––––––––––––––––––––––––––––––––––––––

1. Пусть N – общее число людей (точек).
2. Найдём M – максимальное число точек, лежащих на одной прямой.
3. Обозначим K = N - M.
4. Тогда искомое максимальное число «счастливых» троек:
   • Если M ≤ 2K, ответ = ⌊N / 3⌋.
   • Иначе ответ = K.

Почему так?
• Когда слишком много точек (M) лежит на одной прямой, каждую «счастливую» тройку нужно «разбавлять» точками снаружи прямой. Если M очень велико, окажется, что лимитирующим фактором станет как раз количество «внешних» точек (K).
• Если же прямая не слишком «перегружена» (M ≤ 2K), то мы можем спокойно разбить все точки на тройки (каждая тройка – невырожденный треугольник) и достичь классического максимума ⌊N/3⌋.

––––––––––––––––––––––––––––––––––––––––––
Код на Python
––––––––––––––––––––––––––––––––––––––––––

python
def solve():
    import sys
    from math import gcd
    
    data = sys.stdin.read().strip().split()
    N = int(data[0])
    coords = list(map(int, data[1:]))

    # Если меньше трёх точек, треугольник не построить
    if N < 3:
        print(0)
        return
    
    # Считаем координаты в список кортежей
    points = [(coords[2*i], coords[2*i+1]) for i in range(N)]

    M = 1  # Максимальное число точек на одной прямой
    for i in range(N):
        slope_count = {}  # (dx, dy) -> сколько точек
        local_max = 0
        x_i, y_i = points[i]

        # Считаем все направления от текущей точки
        for j in range(i+1, N):
            x_j, y_j = points[j]
            dx = x_j - x_i
            dy = y_j - y_i

            # Нормализуем (dx, dy), чтобы учесть одинаковые наклоны
            if dx == 0:
                slope = (0, 1)      # Вертикальная
            elif dy == 0:
                slope = (1, 0)      # Горизонтальная
            else:
                g = gcd(dx, dy)
                dx //= g
                dy //= g
                # Приведём к единому знаку
                if dx < 0:
                    dx = -dx
                    dy = -dy
                elif dx == 0 and dy < 0:
                    dy = -dy
                slope = (dx, dy)

            slope_count[slope] = slope_count.get(slope, 0) + 1
            local_max = max(local_max, slope_count[slope])
        
        # local_max точек + сама точка i
        M = max(M, local_max + 1)
        if M == N:  # Больше не найти, прерываем
            break

    # Применяем формулу
    K = N - M
    if M <= 2 * K:
        print(N // 3)
    else:
        print(K)

Ниже приведено упрощённое объяснение задачи и короткий код на Python.

──────────────────────────────────────

1. Пояснение задачи ──────────────────────────────────────

• У нас есть строка, состоящая только из букв R, S, M.
• Антон считает любую «тройку» (набор из трёх букв R, S, M) «правильной», если в ней, при чтении слева направо, символ R встречается раньше, чем символ M (если и R, и M там вообще присутствуют).
• Нужно проверить, не нарушается ли это правило нигде в строке.

Главная идея:
Чтобы нигде не было тройки, в которой M идёт раньше R, в самой строке вообще не должно встречаться ситуация, когда буква M стоит левее какой-то буквы R. Иначе можно было бы «подхватить» эти буквы (и при необходимости букву S) в некую тройку, и там M оказался бы раньше R.

Значит, строка будет «правильной» тогда и только тогда, когда все R идут (по порядку в строке) раньше всех M. Буквы S, где бы они ни стояли, на это правило не влияют.

Иными словами, если хотя бы однажды встретили M, то после этого уже не должно быть ни одного R.

────────────────────────────────────── 2) Простое решение ──────────────────────────────────────

Алгоритм:

1. Сканируем строку слева направо.
2. Как только впервые видим букву M, «запоминаем» это.
3. Если после того, как мы уже встретили M, вдруг встречаем R, значит правило нарушено.

────────────────────────────────────── 3) Код на Python ──────────────────────────────────────

python
def is_correct_string(s: str) -> bool:
    saw_m = False
    for ch in s:
        if ch == 'M':
            saw_m = True
        elif ch == 'R':
            if saw_m:
                # Уже видели M, а теперь встретили R
                # => строка неправильна
                return False
    # Если дошли до конца без нарушений:
    return True

def solve():
    import sys
    s = sys.stdin.read().strip()
    if is_correct_string(s):
        print("YES")
    else:
        print("NO")

Всё, что делает функция is_correct_string: смотрит, не появляется ли R после первого M. Если нет (то есть все R идут до всех M), возвращает True.

python
def solve():
    import sys
    import bisect

    input_data = sys.stdin.read().strip().split()
    n = int(input_data[0])
    amounts = list(map(int, input_data[1:]))

    # -----------------------------------
    # 1) Предварительно вычислим все возможные
    # суммы ровно из трех различных степеней двойки,
    # которые не превышают 10^18.
    # -----------------------------------
    MAX_A = 10**18
    powers = []
    for i in range(61):  # 2^60 ~ 1.15e18
        val = 1 << i
        if val > MAX_A:
            break
        powers.append(val)
    
    possible_sums = []
    length = len(powers)
    for i in range(length):
        for j in range(i+1, length):
            for k in range(j+1, length):
                s = powers[i] + powers[j] + powers[k]
                if s <= MAX_A:
                    possible_sums.append(s)
                else:
                    # Так как при увеличении k сумма только растёт,
                    # можно прервать внутренний цикл
                    break

    # Отсортируем все полученные суммы
    possible_sums.sort()

    # -----------------------------------
    # 2) Для каждой из n сумм a^i найдём
    # максимально возможную сумму из нашего списка,
    # которая не превышает a^i.
    # -----------------------------------
    import bisect
    for a_i in amounts:
        # Ищем индекс, где можно было бы вставить a_i + 1,
        # чтобы результат оставался отсортированным
        idx = bisect.bisect_right(possible_sums, a_i)
        if idx == 0:
            # Нет ни одного значения <= a_i
            print(-1)
        else:
            # idx - 1 указывает на последний элемент,
            # не превосходящий a_i
            print(possible_sums[idx - 1])

Пояснения по решению:

1. Генерируем все мощности двойки до 2^60 (это чуть больше 10^18).
2. Перебираем тройки различных степеней двойки, суммируем их и отбрасываем те, что превышают 10^18. Получается список всех возможных сумм из трёх уникальных цветов (цены-степени двойки).
3. Сортируем полученный список (он не слишком велик, максимум C(61, 3) ≈ 35990).
4. Для каждого запроса a^i (количество денег Бориса на i-й день) бинарным поиском находим наибольшую сумму в этом списке, не превосходящую a^i. Если такой суммы нет, отвечаем -1.

Ниже приведён разбор задачи и один из возможных вариантов кода на Python (с краткими комментариями). Основная идея решения основана на том, что сумма по всем парам (ai + aj)^p (при i < j) может быть вычислена гораздо быстрее, чем напрямую за O(n^2).

──────────────────────────────────────────────────────────────────

1. Формула для f(p) = ∑(i<j) (ai + aj)^p ──────────────────────────────────────────────────────────────────

Отметим, что (ai + aj)^p симметрично по (i, j). Поэтому:
∑(i<j) (ai + aj)^p = ½ ⋅ ∑(i≠j) (ai + aj)^p
Тогда рассмотрим полную двойную сумму (включая i = j):
∑(i,j) (ai + aj)^p = ∑(i=1..n) ∑(j=1..n) (ai + aj)^p
Без ограничения i ≠ j она раскладывается через биномиальный коэффициент:
(ai + aj)^p = ∑(r=0..p) C(p,r) ⋅ ai^r ⋅ aj^(p-r),
где C(p,r) — биномиальный коэффициент "p choose r".

Тогда:
∑(i,j) (ai + aj)^p
= ∑(r=0..p) [ C(p,r) ⋅ (∑(i) ai^r) ⋅ (∑(j) aj^(p-r)) ]
= ∑(r=0..p) [ C(p,r) ⋅ S_r ⋅ S_{p-r} ],
где S_r = ∑(i=1..n) (ai^r) — сумма r-х степеней всех ai.

Теперь нужно исключить случаи i = j, то есть вычесть (ai + ai)^p = (2 ai)^p для всех i. Сумма по i = j даёт:
∑(i=1..n) (2⋅ai)^p = ∑(i=1..n) 2^p ⋅ (ai^p) = 2^p ⋅ S_p.

Таким образом:
∑(i≠j) (ai + aj)^p
= ( ∑(r=0..p) C(p,r) ⋅ S_r ⋅ S_{p-r} ) – 2^p ⋅ S_p.

А поскольку нам нужна только сумма по i < j (а не i ≠ j), то делим результат пополам:
f(p) = ∑(i<j) (ai + aj)^p
= ½ ⋅ [ ∑(r=0..p) C(p,r) ⋅ S_r ⋅ S_{p-r} – 2^p ⋅ S_p ].

Все вычисления делаются по модулю M = 998244353.

────────────────────────────────────────────────────────────────── 2) Как считать S_r = ∑(i=1..n) ai^r (для r=0..k) ──────────────────────────────────────────────────────────────────

• S_0 = n (поскольку ai^0 = 1 для любого ai≠0).
• Для r ≥ 1 достаточно последовательно умножать по модулю.
Например, заведём массив curPower[i], в котором хранится текущее ai^r для r−1. Изначально curPower[i]=1 (это ai^0).
Для очередного r делаем:
– для каждого i: curPower[i] = (curPower[i] * ai) mod M,
– суммируем curPower[i] по всем i, чтобы получить S_r.

Такой способ занимает O(n⋅k) умножений. При n до 2·10^5 и k до 300 это даёт порядка 6·10^7 умножений, что на пределе для Python. В некоторых средах (особенно PyPy) это может пройти при аккуратной оптимизации (быстрая работа со вводом/выводом, возможно слегка оптимизированные операции). В C++ такой код, как правило, проходит достаточно легко.

Если же тесты очень жёсткие, то для Python могут потребоваться дополнительные оптимизации (использование pypy, написание частей кода на Cython и т.п.). Тем не менее, представленный код иллюстрирует сам метод.

────────────────────────────────────────────────────────────────── 3) Вычисление биномиальных коэффициентов и 2^p по модулю ──────────────────────────────────────────────────────────────────

• Биномиальные коэффициенты C(p, r) для p ≤ k можно заранее вычислить в таблице (k+1)×(k+1) стандартной треугольной формулой C(n, r) = C(n−1, r−1) + C(n−1, r).
• Степени двойки 2^p тоже заранее считаем в массиве pow2[p].

────────────────────────────────────────────────────────────────── 4) Финальная формула и код ──────────────────────────────────────────────────────────────────

Итог:
f(p) = ( 1/2 ) * [ ∑(r=0..p) C(p,r)S_rS_{p-r} – 2^p*S_p ] mod M,
где деление на 2 по модулю M делается умножением на inv2 = (M+1)//2 (так как 998244353 — простое, у двойки есть обратный элемент).

Ниже приведён код на Python, реализующий описанную идею:

────────────────────────────────────────────────────────────────── КОД ──────────────────────────────────────────────────────────────────

python
def solve():
    import sys
    input_data = sys.stdin.read().strip().split()
    
    MOD = 998244353
    
    # Читаем n, k
    n, k = map(int, input_data[:2])
    arr = list(map(int, input_data[2:] ))
    
    # -------------------------------
    # 1) Считаем S_r = sum_i (arr[i]^r) для r=0..k
    #    - используем поэтапное умножение
    # -------------------------------
    S = [0]*(k+1)
    
    # curPower[i] будет хранить текущую степень arr[i]^(r),
    # и пойдём по r по возрастанию
    curPower = [1]*n  # r=0 => arr[i]^0 = 1
    S[0] = n % MOD    # Сумма всех 1
    
    # Для r = 1..k последовательно умножаем
    idx = 0
    for r in range(1, k+1):
        s = 0
        for i in range(n):
            # умножаем на arr[i] по модулю
            curPower[i] = (curPower[i] * arr[i]) % MOD
            s = (s + curPower[i]) % MOD
        S[r] = s
    
    # -------------------------------
    # 2) Предвычислим биномиальные коэффициенты C(p,r)
    #    для p до k с помощью треугольника Паскаля
    # -------------------------------
    C = [[0]*(k+1) for _ in range(k+1)]
    C[0][0] = 1
    for p in range(1, k+1):
        C[p][0] = 1
        for r in range(1, p+1):
            C[p][r] = (C[p-1][r-1] + C[p-1][r]) % MOD
    
    # -------------------------------
    # 3) Предвычислим степени двойки 2^p (p=0..k)
    # -------------------------------
    pow2 = [1]*(k+1)
    for p in range(1, k+1):
        pow2[p] = (pow2[p-1] * 2) % MOD
    
    # Обратный элемент к 2 по модулю:
    inv2 = (MOD+1)//2  # так как MOD простое, это 2^(MOD-2) % MOD
    
    # -------------------------------
    # 4) Вычисляем f(p) для p=1..k
    #    f(p) = (1/2) * [ sum_{r=0..p} C(p,r)*S_r*S_{p-r} - 2^p * S_p ]
    # -------------------------------
    # Выводим результат для каждого p
    # (каждое в новой строке)
    idx_out = 0
    out = []
    for p in range(1, k+1):
        # Считаем sum_{r=0..p} C(p,r)*S_r*S_{p-r} (mod M)
        val = 0
        for r in range(p+1):
            val += C[p][r] * S[r] * S[p-r]
        val %= MOD
        
        # Вычитаем 2^p * S_p
        val -= pow2[p]*S[p]
        val %= MOD
        
        # теперь умножаем на 1/2 (то есть на inv2)
        val = (val * inv2) % MOD
        
        out.append(str(val))
    
    print("\n".join(out))

Основные шаги кода:
• Сначала мы вычисляем все S[r], r=0..k.
• Затем готовим биномиальные коэффициенты C(p, r) и степени двойки 2^p.
• Наконец, по формуле считаем f(p) для p=1..k и выводим.

Если проблема в скорости на больших тестах, такие задачи чаще решают на более быстрых языках (C++/Rust) или с помощью PyPy. В любом случае, ключевой момент – использование математической формулы, позволяющей не перебирать все пары напрямую за O(n^2).

python
def solve():
    import sys
    import bisect

    data = sys.stdin.read().strip().split()
    n = int(data[0])
    budgets = list(map(int, data[1:]))

    # -----------------------------------
    # 1) Сформируем все цены цветов как 2^i, где i=0..60
    #    (2^60 ~ 1.15e18, чуть больше 1e18, но возьмём до 60 включительно)
    # -----------------------------------
    powers = []
    for i in range(61):
        cost = 1 << i
        # 2^60 ~ 1.15e18, что всё ещё приемлемо для сравнения,
        # не будем отбрасывать заранее.
        powers.append(cost)

    # -----------------------------------
    # 2) Соберём все возможные суммы из трёх РАЗНЫХ цветов (i<j<k)
    #    При этом храним только суммы <= 1e18
    # -----------------------------------
    possible_sums = []
    length = len(powers)
    LIMIT = 10**18
    for i in range(length):
        for j in range(i+1, length):
            s_ij = powers[i] + powers[j]
            if s_ij > LIMIT:
                # Раз дальше только увеличивается, смысла нет продолжать по j
                break
            for k in range(j+1, length):
                s = s_ij + powers[k]
                if s <= LIMIT:
                    possible_sums.append(s)
                else:
                    # Дальше сумма только растёт, прерываем внутренний цикл
                    break

    # Отсортируем все такие суммы
    possible_sums.sort()

    # -----------------------------------
    # 3) Для каждого дня (каждого бюджета) найдём
    #    максимально возможную сумму (<= a_i)
    #    или выведем -1, если никакая тройка не проходит.
    # -----------------------------------
    out = []
    for money in budgets:
        # bisect_right даёт позицию, куда можно вставить money+1,
        # чтобы сохранить порядок
        idx = bisect.bisect_right(possible_sums, money)
        if idx == 0:
            # Ни одна тройка не укладывается в money
            out.append("-1")
        else:
            # possible_sums[idx-1] — наибольшая сумма, не превосходящая money
            out.append(str(possible_sums[idx-1]))

    print("\n".join(out))

Описание решения (коротко):

1. Генерируем степени двойки 2^i, i = 0..60.
2. Для всех тройных индексов (i<j<k) считаем сумму 2^i + 2^j + 2^k и, если она ≤ 10^18, сохраняем в список.
3. Сортируем список возможных сумм.
4. Для каждого бюджета a_i ищем бинарным поиском наибольшую сумму в списке, не превосходящую a_i. Если такой нет, печатаем −1, иначе печатаем найденную сумму.