Предметный тур. Информатика. 3 этап

Используем условный оператор для реализации логики, описанной в условии задачи. Чтобы определить, делится ли \(x\) на \(y\), можно проверить, выполняется ли условие \(x \% y == 0\). Здесь \(x \% y\) обозначает остаток от деления \(x\) на \(y\), где \(\%\) — оператор, который находит остаток.

Если \(x\) делится на \(y\), то остаток от деления \(x\) на \(y\) равен \(0\), поэтому приведенный выше код определяет делимость.

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

Пример программы-решения

Ниже представлено решение на языке Python.

y = int(input())
if y % 4:
    print(365 * 60 * 24)
else:
    if y % 100:
        print(366 * 60 * 24)
    else:
        if y % 400:
            print(365 * 60 * 24)
        else:
            print(366 * 60 * 24)

Имеем:

\[\sum\limits_{i=1}^{a} \sum\limits_{j=1}^{b} \sum\limits_{k=1}^{c} i \cdot j \cdot k = \sum\limits_{i=1}^{a} i \cdot \sum\limits_{j=1}^{b} j \cdot \sum\limits_{k=1}^{c} k = \frac{a(a+1)}{2} \cdot \frac{b(b+1)}{2} \cdot \frac{c(c+1)}{2}.\]

Пример программы-решения

Ниже представлено решение на языке Python.

a, b, c = map(int, input().split())
sum = a * (a + 1) // 2 * b * (b + 1) // 2 * c * (c + 1) // 2
print(sum % 998244353)

Пусть:

• \(a_i\) — общее количество элементов (толщина) угощения ранга \(i\) (\(i \geqslant 0\)),
• \(p_i\) — количество элементов «Чистая энергия» (E) в угощении ранга \(i\) (\(i \geqslant 0\)).

Эти величины вычисляются рекуррентно: \[\begin{cases} a_0 = 1 & \text{(только E)}, \\ a_i = 2a_{i-1} + 3 & \text{при } i \geqslant 1, \end{cases} \quad \begin{cases} p_0 = 1 & \text{(только E)}, \\ p_i = 2p_{i-1} + 1 & \text{при } i \geqslant 1. \end{cases}\]

Искомое количество элементов «Чистая энергия» в верхних \(X\) слоях угощения ранга \(N\) обозначим как \(f(N, X)\).

Угощение ранга 0 — это просто E: \[f(0, X) = \begin{cases} 1 & \text{при } X \geqslant 1, \\ 0 & \text{при } X = 0. \end{cases}\]

Угощение ранга \(N\) имеет структуру: \[\text{M} + \text{Угощение}_{N-1} + \text{E} + \text{Угощение}_{N-1} + \text{M}.\]

Разберем возможные значения \(X\):

1. \(X = 1: f(N, 1) = 0\) (верхний слой — M).
2. \(1 < X \leqslant 1 + a_{N-1}: f(N, X) = f(N-1, X - 1)\).
3. \(X = 2 + a_{N-1}: f(N, X) = p_{N-1} + 1\).
4. \(2 + a_{N-1} < X \leqslant 2 + 2a_{N-1}: f(N, X) = p_{N-1} + 1 + f(N-1, X - (2 + a_{N-1}))\).
5. \(X \geqslant 3 + 2a_{N-1}: f(N, X) = 2p_{N-1} + 1\).

Если реализовать это как рекурсивную функцию, то ответ может быть найден за \(N + 1\) шагов вычислений.

Пример программы-решения

Ниже представлено решение на языке Python.

N, X = map(int, input().split())
a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])

print(f(N, X))

Очевидно, что в случае \(s = n\) ответом будет \(n + 1\).

В остальных случаях сначала проводится полный перебор для нахождения целого числа \(b\) в диапазоне \(2 \leqslant b \leqslant \sqrt{n}\), удовлетворяющего условию \(f(b, n) = s\). Если такое \(b\) существует, то минимальное из них будет ответом.

Если такого \(b\) не найдено, то необходимо проверить наличие целого числа \(b\) в диапазоне \(\sqrt{n} < b \leqslant n\), удовлетворяющего условию \(f(b, n) = s\). Заметим, что при \(b > \sqrt{n}\) число \(n\) в системе счисления с основанием \(b\) будет двузначным. Пусть старшая цифра будет \(p\), а младшая — \(q\) (где \(1 \leqslant q < b\), \(0 \leqslant q < b\)), тогда \[\label{eq:inf_bd_01} n = p \cdot b + q.\]

Согласно условию задачи,

\[\label{eq:inf_bd_02} p + q = s.\]

Поскольку \(b > \sqrt{n}\), из уравнения \eqref{eq:inf_bd_01} следует, что \(n = p \cdot b + q \geqslant p \cdot b > p^2\), откуда получаем \(p < \sqrt{n}\). Таким образом можно провести полный перебор по старшей цифре \(p\). Из уравнений \eqref{eq:inf_bd_01} и \eqref{eq:inf_bd_02} следует, что \(b = \dfrac{n - s}{p} + 1\), поэтому \(b\) однозначно определяется по \(p\). Наконец, для такого \(b\) необходимо проверить, выполняется ли условие \(f(b, n) = s\).

Общая сложность алгоритма составляет \(\mathcal{O}(\sqrt{n})\), что позволяет получить максимальный балл.

Пример программы-решения

Ниже представлено решение на языке Python.

def sum_digit(b, n):
    if n < b:
        return n
    return sum_digit(b, n // b) + n % b
 
N = int(input())
S = int(input())
 
if S > N:
    print(-1)
elif S == N:
    print(N + 1)
else:
    sqrt = int(pow(N, 0.5))
    for b in range(2, sqrt + 1):
        if sum_digit(b, N) == S:
            print(b)
            quit()
    for k in reversed(range(1, sqrt + 1)):
        if (N - S) % k == 0:
            b = (N - S) // k + 1
            if sum_digit(b, N) == S:
                print(b)
                quit()
    print(-1)

Найдем ответ бинарным поиском по ответу следующим образом. Предположим, что сможем получить высоту \(h\). Тогда посчитаем, сколько понадобится песка, чтобы ее построить. Если есть необходимое количество, такая высота горы устраивает.

Чтобы по данному \(h\) определить необходимое количество песка, переберем всевозможные \(i\), где может находиться вершина горы. Чтобы считать количество песка быстрее, заведем три вспомогательных массива: массив префиксных сумм \({psum}\) (для быстрого подсчета суммы высот каменных столбов), массив \({left}\) и массив \({right}\). Два последних массива понадобятся пересчитывать для каждого \(h\).

Массив \({left}\) — это такой массив, что \({left}[i]\) — координата левой границы насыпи из песка, если вершина насыпи высоты \(h\) находится на координате \(i\). Будем строить его следующим образом: для каждой координаты \(i\) посчитаем, для какой координаты \({sfrom}\) она может быть левой границей насыпи (чтобы \({left}[{sfrom}] = i\)). Если будем перебирать \(i\) слева, то для каждой координаты \({sfrom}\) значение \({left}[{sfrom}]\) будет максимальным, что и требуется. Аналогично построим массив \({right}\) — координаты правых границ насыпей.

После этого остается перебрать всевозможные координаты вершины и для каждой посчитать размер горы высоты \(h\) (учитывая камни). Это можно сделать по формуле, так как известно, где каждая гора начинается (по массиву \({left}\)) и заканчивается (по массиву \({right}\)). Затем остается вычесть количество камней в полученной горе (с помощью \({psum}\)) и найти минимум среди полученных значений.

Пример программы-решения

Ниже представлено решение на языке Python.

import sys

inf = int(2e18)
N = 123456

h = [0] * N
ev = [[] for _ in range(N)]
ans = [0] * N
sum = [0] * N

def main():
    n, m = map(int, sys.stdin.readline().split())
    for i in range(n):
        h[i] = int(sys.stdin.readline().strip())
    
    low = 0
    for i in range(n):
        low = max(low, h[i])
    
    high = int(1.01e9)
    while low < high:
        mid = (low + high + 1) // 2
        for i in range(n):
            ans[i] = 0
        
        for rot in range(2):
            sum[0] = h[0]
            for i in range(1, n):
                sum[i] = sum[i - 1] + h[i]
            
            for i in range(n):
                ev[i].clear()
            
            for i in range(n):
                j = i + mid - h[i]
                if j < n:
                    ev[j].append(i)
            
            mx = -1
            for i in range(n):
                for j in range(len(ev[i])):
                    mx = max(mx, ev[i][j])
                if mx >= 0:
                    from_val = mid - 1
                    to = mid - (i - mx) + 1
                    ans[i] += (to + from_val) * (from_val - to + 1) // 2
                    ans[i] -= (sum[i - 1] - sum[mx])
                else:
                    ans[i] += inf
            
            for i in range(n // 2):
                h[i], h[n - i - 1] = h[n - i - 1], h[i]
                ans[i], ans[n - i - 1] = ans[n - i - 1], ans[i]
        
        found = False
        for i in range(n):
            ans[i] += mid - h[i]
            if ans[i] <= m:
                found = True
                break
        
        if found:
            low = mid
        else:
            high = mid - 1
    
    print(low)

if __name__ == "__main__":
    main()