4d-report.js

/*

D. Рапорт

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

Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из a[i] букв, вторая — m слов, j-е из которых состоит из b[j] букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.

Обе части рапорта записываются аналогично, каждая на своей части рулона. Одна буква слова занимает ровно одну клетку. Первое слово записывается в первой строке рулона, начиная с самой левой клетки этой части рулона. Каждое следующее слово, если это возможно, должно быть записано в той же строке, что и предыдущее, и быть отделено от него ровно одной пустой клеткой. Иначе, оно пишется в следующей строке, начиная с самой левой клетки. Если ширина части рулона меньше, чем длина какого-то слова, которое должно быть написано в этой части, написать эту часть рапорта на части рулона такой ширины невозможно.

Гарантируется, что можно провести вертикальную черту так, что обе части рапорта возможно написать. Верс хочет провести вертикальную черту так, чтобы длина рулона, которой хватит, чтобы написать рапорт, была минимальна. Помогите ей найти эту минимальную длину.

Формат ввода
В первой строке даны три целых числа w, n и m — ширина рулона, количество слов в первой и второй части рапорта (1 ≤ w ≤ 10^9; 1 ≤ n, m ≤ 100000).
В следующей строке дано n целых чисел a[i] — длина i-го слова первой части рапорта 1 ≤ a[i] ≤ 10^9.
В следующей строке дано m целых чисел b[j] — длина j-го слова второй части рапорта 1 ≤ b[j] ≤ 10^9.
Гарантируется, что возможно провести черту так, что обе части рапорта возможно написать.

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

Пример

Ввод
15 6 6
2 2 2 3 2 2
3 3 5 2 4 3

Вывод
3

Примечания
В тесте из примера рулон можно разделить на две части, проведя черту между 7 и 8 столбцом клеток, а затем записать по два слова в каждой строке в обеих частях рапорта.

*/

const fs = require('fs');

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

const [totalWidth, firstPartSize, secondPartSize] = input[0].trim().split(' ').map((value) => parseInt(value));

const longestWordWidths = [0, 0];
const wordArrays = [new Array(firstPartSize), new Array(secondPartSize)];

for (let part = 1; part <= 2; ++part) {
    const dataString = input[part].trim() + ' ';
    const length = dataString.length;

    let valueString = '';
    let valueCount = 0;

    for (let pos = 0; pos < length; ++pos) {
        if (dataString[pos] === ' ') {
            const valueNumber = parseInt(valueString);
            if (valueNumber > longestWordWidths[part - 1]) {
                longestWordWidths[part - 1] = valueNumber;
            }

            wordArrays[part - 1][valueCount] = valueNumber;

            ++valueCount;
            valueString = '';
        } else {
            valueString += dataString[pos];
        }
    }
}

function calculateLines(part, width) {
    const wordArray = wordArrays[part];
    let sum = wordArray[0];
    let count = 1;
    for (let w = 1; w < wordArray.length; ++w) {
        sum += wordArray[w] + 1;
        if (sum > width) {
            sum = wordArray[w];
            ++count;
        }
    }

    return count;
}

let minHeight = Infinity;
let leftPartLines = 0;
let rightPartLines = 0;

function check(center) {
    leftPartLines = calculateLines(0, center);
    rightPartLines = calculateLines(1, totalWidth - center);

    const height = Math.max(leftPartLines, rightPartLines);
    if (height < minHeight) {
        minHeight = height;
    }

    return leftPartLines <= rightPartLines;
}

let left = longestWordWidths[0];
let right = totalWidth - longestWordWidths[1];
let middle = 0;

while (left < right) {
    middle = Math.floor((left + right) / 2);
    if (check(middle)) {
        right = middle;
    } else {
        left = middle + 1;
    }
}

check(left);

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