소프티어

• 적합한 세트 수가 나올 때 까지 탐색을 진행해야 함
• 0~ 하기에는 O(n)이며, n이 너무 너무 너무 큼. 1초에 10억번의 연산을 진행해도, 2조 번의 연산에 2,000초 (30분) 소모
• 그래서 이진 탐색을 통해 범위를 좁힌다면, O(log n). 최대 41번의 연산을 통해 값을 구할 수 있게 됨.

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/);
const [N, T] = input[0].split(' ').map(Number);
const scenarios = input.slice(1).map(scenario => scenario.split(' ').map(Number));

function test(list, count) {
    let prevValue = 0
    for(let i = 0; i < list.length; i += 2) {
        if (prevValue + list[i] >= count) {
            prevValue = list[i + 1] || 0
        }
        else if (prevValue + list[i] + (list[i + 1] || 0) >= count) {
            prevValue = prevValue + list[i] + (list[i + 1] || 0) - count
        }
        else {
            return false
        }
    }
    return true
}

function binarySearch(start, end, list) {
    // 이건 더이상 탐색이 불가능할때까지 진행해야함
    // 나는 start 에 정답이 나오게 하겠다.
    // 그럼 mid 가 true 이면 start 에는 mid 를
    // mid 가 false 이면 end 에 mid 를 넣어서
    // end 는 정답이 아니고 start 가 정답이 되게
    while (true) {
        if (start + 1 === end) {
            return start
        }

        const mid = Math.floor((start + end) / 2)
        const result = test(list, mid)

        if (result) {
            start = mid
        }
        else {
            end = mid
        }
    }
}

const output = []
scenarios.forEach((scenario, i) => {
    // start 에 정답이 모이게 했으니 최소 값 0을
    // end 에는 정답이 아닌 것이 오게 했고,
    // 단순히 각 난이도의 최대 문제 개수 (10 ** 12)를 해주면 에러가 남
    // 왜냐하면 모든 애매한 난이도 문제의 옮겨지는 것까지 포함하면 (10 ** 12) 이 2배 된다고 보는게 편함
    const t = binarySearch(0, 2 * (10 ** 12), scenario);
    output.push(t)
});
console.log(output.join('\n'))