4b-one-dimensional-sea-battle.js

/*

B. Одномерный морской бой

Ограничение времени	2 секунды (фактическое использование на тестах – до 77ms)
Ограничение памяти	256Mb (фактическое использование на тестах – до 5.51Mb)
Ввод	стандартный ввод или input.txt
Вывод	стандартный вывод или output.txt

Поле в игре в одномерный морской бой имеет размеры 1×n. Ваша задача — найти такое максимальное k, что на поле можно расставить один корабль размера 1×k, два корабля размера 1×(k−1), …, k кораблей размера 1×1, причем корабли, как и в обычном морском бое, не должны касаться друг друга и пересекаться.

Формат ввода
В единственной строке входных данных дано число n — количество клеток поля (0 ≤ n ≤ 10^18).

Формат вывода
Выведите единственное число — такое максимальное k, что можно расставить корабли, как описано в условии.

Пример

Ввод
7

Вывод
2

Примечания
Пояснение к примеру: для поля 1×7 ответ равен 2. Расставить один корабль размера 1×2 и два корабля размера 1×1 можно следующим образом:
[#][#][ ][#][ ][#][ ]

*/

const fs = require('fs');

const input = fs.readFileSync('input.txt', 'utf8').toString().trim();

const size = BigInt(input);

function calculateSize(value) {
    const multiplier = (value ** 2n + 3n * value) / 2n;
    const decreaser = value * (2n * value + 5n) * (value - 1n) / 6n + 1n;
    return value * multiplier - decreaser;
}

let left = 0n;
let right = size;
let middle;

while (left < right) {
    middle = (left + right + 1n) / 2n;
    if (calculateSize(middle) <= size) {
        left = middle;
    } else {
        right = middle - 1n;
    }
}

let result = left;

fs.writeFileSync('output.txt', `${result}`);