1. Идея

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

Для высоты k требуется:

1 + 2 + ... + k = k * (k + 1) / 2

Значит, надо найти минимальное k, такое что

k * (k + 1) / 2 >= X

Перебирать k по одному слишком долго, потому что X может быть до 10^18. Поэтому используем двоичный поиск по ответу.

2. Наблюдения

Наблюдение 1

Функция

f(k) = k * (k + 1) / 2

строго возрастает при увеличении k.

Это очень важно: если для некоторого k уже выполнено f(k) >= X, то для всех больших k это тоже будет выполнено.

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

Значит, ответы имеют вид:

• сначала идут все k, для которых условие ложно;
• потом идут все k, для которых условие истинно.

Такую границу очень удобно искать двоичным поиском.

Наблюдение 2

Нужно подобрать правую границу поиска r, которая точно содержит ответ.

В эталонном решении взято r = 2000000000.

Этого достаточно, потому что при k = 2 * 10^9 значение k * (k + 1) / 2 уже намного больше 10^18, значит ответ точно не превосходит этой границы.

3. Алгоритм

Будем поддерживать отрезок [l, r], в котором находится ответ.

1. Считываем X.
2. Берём:
   • l = 1
   • r = 2000000000
3. Пока l < r:
   • находим середину m = (l + r) // 2;
   • считаем s = m * (m + 1) // 2;
   • если s >= X, значит m уже подходит, и ответ находится в левой части, включая m, поэтому r = m;
   • иначе m не подходит, значит ответ строго правее, поэтому l = m + 1.
4. Когда цикл закончится, l == r, это и есть минимальное подходящее k.
5. Выводим l.

4. Почему это работает

Докажем, что алгоритм действительно находит минимальное k, для которого

k * (k + 1) / 2 >= X.

Обозначим условие good(k): good(k) истинно, если k * (k + 1) / 2 >= X.

Свойство монотонности

Так как сумма 1 + 2 + ... + k растёт с увеличением k, функция good(k) монотонна:

• если good(k) истинно, то good(k + 1), good(k + 2) и так далее тоже истинны;
• если good(k) ложно, то для всех меньших k оно тоже ложно.

Значит, существует минимальное значение k, начиная с которого условие становится истинным. Именно его и нужно найти.

Что поддерживает двоичный поиск

На каждом шаге ответ находится внутри текущего отрезка [l, r].

Рассмотрим середину m.

Случай 1: good(m) истинно

Тогда m уже подходит, но, возможно, существует ещё меньший подходящий ответ. Значит, искомое минимальное значение лежит в отрезке [l, m]. Поэтому можно заменить r = m.

Случай 2: good(m) ложно

Тогда m не подходит, и из монотонности следует, что не подходят и все значения слева от него. Значит, ответ лежит в отрезке [m + 1, r]. Поэтому можно заменить l = m + 1.

На каждом шаге длина отрезка уменьшается, поэтому процесс обязательно закончится.

Когда l == r, в отрезке осталось ровно одно число. Оно и является минимальным k, для которого условие истинно.

5. Сложность

На каждом шаге двоичного поиска отрезок уменьшается примерно вдвое.

Так как правая граница равна 2 * 10^9, количество итераций порядка log2(2 * 10^9), то есть около 31.

• Время работы: O(log 2*10^9), фактически O(log X) по смыслу задачи
• Память: O(1)

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long X;
    cin >> X;

    long long l = 1;
    long long r = 2000000000LL;

    while (l < r) {
        long long m = l + (r - l) / 2;
        long long sum = m * (m + 1) / 2;
        if (sum >= X) {
            r = m;
        } else {
            l = m + 1;
        }
    }

    cout << l << '\n';
    return 0;
}

7. Код на Python 3

x = int(input())

l = 1
r = 2_000_000_000

while l < r:
    m = (l + r) // 2
    s = m * (m + 1) // 2
    if s >= x:
        r = m
    else:
        l = m + 1

print(l)