3j-p2p-update.js

/*

J. P2P обновление

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

В системе умного дома под управлением голосового помощника Лариса n устройств, соединяющихся между собой по сети LoRaWAN. Устройство номер 1 подключено к интернету и на него было скачано обновление, которое необходимо передать на все устройства.

Сеть LoRaWAN очень медленная, поэтому для распространения протокола был придуман peer-to-peer (P2P) протокол. Файл обновления разбивается на k одинаковых по размеру частей, занумерованных от 1 до k.

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

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

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

После того, как все запросы отправлены, каждое устройство выбирает, чей запрос удовлетворить. Устройство A удовлетворяет тот запрос, который поступил от наиболее ценного для A устройства. Ценность устройства B для устройства A определяется как количество частей обновления, ранее полученных устройством A от устройства B. Если на устройство A пришло несколько запросов от одинаково ценных устройств, то удовлетворяется запрос того устройства, на котором меньше всего скачанных частей обновления. Если и таких запросов несколько, то среди них выбирается устройство с наименьшим номером.

Далее начинается новый таймслот. Устройства, чьи запросы удовлетворены, скачивают запрошенную часть обновления, а остальные не скачивают ничего.

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

Формат ввода
Вводится два числа n и k (2 ≤ n ≤ 100, 1 ≤ k ≤ 200).

Формат вывода
Выведите n-1 число — количество таймслотов, необходимых для скачивания обновления на устройства с номерами от 2 до n.

Пример

Ввод
3 2

Вывод
3 3

Примечания

Для удобства будем пользоваться обозначениями устройств буквами A, B, C (соответствует устройствам с номерами 1, 2 и 3). На устройстве A есть обе части обновления, а на устройствах B и C — ни одной.

Перед первым таймслотом для каждой части определяется количество устройств, на которых скачана каждая часть обновления: и 1 и 2 часть обновления присутствуют только на одном устройстве.

Устройства B и C выбирают самую редкую отсутствующую у них часть обновления с минимальным номером: самая редкая часть с минимальным номером — это часть 1. Она отсутствует и на устройстве B, и на устройстве С. Они запрашивают ее у устройства A. Ценность устройств B и C для устройства A равна нулю. Количество имеющихся у устройств B и C частей обновления одинакова и равно нулю. Поэтому устройство A выбирает устройство с минимальным номером (B). Во время первого таймслота выполняется передача части 1 с устройства A на устройство B. Ценность устройства A для устройства B становится равной 1.

Перед вторым таймслотом для каждой части определяется количество устройств, на которых скачана каждая часть обновления: самой редкой оказывается часть 2 (присутствует только на устройстве A), следующая по редкости часть 1 (присутствует на устройствах A и B).

Устройства B и C выбирают среди отсутствующих у них частей обновления самую редкую: для обоих устройств выбирается часть 2. Каждое из них делает запрос части 2 у единственного обладателя этой части — устройства A. Ценность устройств B и C для устройства A одинакова и равна нулю. Количество имеющихся у устройства C частей (0) меньше, чем у устройства B (1), поэтому выбирается устройство C. Во время второго таймслота выполняется передача части 2 с устройства A на устройство C. Ценность устройства A для устройства C становится равной 1.

Перед третьим таймслотом для каждой части определяется количество устройств, на которых скачана каждая часть обновления: обе части 1 и 2 присутствуют на двух устройствах (часть 1 на устройствах A и B, часть 2 — на устройствах A и C)

Устройство B может сделать запрос недостающей части 2 у обладающей ей устройств A и C, но выбирает устройство C, т.к. на устройстве C скачано меньше частей (1), чем у устройства A (2).

Устройство C может сделать запрос недостающей части 1 у обладающей ей устройств A и B, но выбирает устройство B, т.к. на устройстве B скачано меньше частей (1), чем у устройства A (2).

Во время третьего таймслота оба запроса оказываются единственными запросами у устройств B и C и удовлетворяются. Часть 2 передается с устройства C на устройство B. Часть 1 передается с устройства B на устройство C. Ценность устройства B для устройства C становится равной 1. Ценность устройства C для устройства B становится равной 1.

Все части обновления оказываются на всех устройствах и на этом обновление заканчивается.

*/

const fs = require('fs');

const [totalDevices, totalChunks] = fs.readFileSync('input.txt', 'utf8').toString().trim().split(' ').map((value) => parseInt(value));

const devicesMap = new Map();
const devicesArray = new Array(totalDevices);
const chunksMap = new Map();
const chunksArray = new Array(totalChunks);
let completedDevices = 1;

for (let i = 0; i < totalDevices; ++i) {
    devicesArray[i] = {
        id: i,
        chunksCount: 0,
        chunksArray: new Array(totalChunks),
        peersRating: new Array(totalDevices).fill(0),
        incomingRequests: [],
        completed: false,
        slots: 0,
    };
    devicesMap.set(i, devicesArray[i]);
}

const firstDevice = devicesArray[0];
firstDevice.chunksCount = totalChunks;
firstDevice.completed = true;

for (let i = 0; i < totalChunks; ++i) {
    chunksArray[i] = {
        id: i,
        count: 1,
    };
    chunksMap.set(i, chunksArray[i]);
    firstDevice.chunksArray[i] = true;
}

while (completedDevices < totalDevices) {
    const requestQueue = [];

    chunksArray.sort((firstChunk, secondChunk) => {
        const firstChunkScore = firstChunk.count * 1000 + firstChunk.id;
        const secondChunkScore = secondChunk.count * 1000 + secondChunk.id;
        return firstChunkScore - secondChunkScore;
    });

    for (let d = 0; d < totalDevices; ++d) {
        const device = devicesArray[d];
        if (device.completed) {
            continue;
        } else {
            ++device.slots;
        }

        const deviceIndex = device.id;
        for (let c = 0; c < totalChunks; ++c) {
            const chunkIndex = chunksArray[c].id;
            if (!device.chunksArray[chunkIndex]) {
                requestQueue.push([chunkIndex, deviceIndex]);
                break;
            }
        }
    }

    if (!requestQueue.length) {
        break;
    }

    devicesArray.sort((firstDevice, secondDevice) => {
        const firstDeviceScore = firstDevice.chunksCount * 1000 + firstDevice.id;
        const secondDeviceScore = secondDevice.chunksCount * 1000 + secondDevice.id;
        return firstDeviceScore - secondDeviceScore;
    });

    for (let r = 0; r < requestQueue.length; ++r) {
        const [chunkIndex] = requestQueue[r];
        for (let d = 0; d < totalDevices; ++d) {
            const device = devicesArray[d];
            if (device.chunksArray[chunkIndex] === true) {
                device.incomingRequests.push(requestQueue[r]);
                break;
            }
        }
    }

    const responseQueue = [];

    for (let d = 0; d < totalDevices; ++d) {
        const emittingDevice = devicesArray[d];

        emittingDevice.incomingRequests.sort(([, firstDeviceIndex], [, secondDeviceIndex]) => {
            const firstDevice = devicesMap.get(firstDeviceIndex);
            const secondDevice = devicesMap.get(secondDeviceIndex);
            const firstDeviceScore = emittingDevice.peersRating[firstDeviceIndex] * -1000000 + firstDevice.chunksCount * 1000 + firstDevice.id;
            const secondDeviceScore = emittingDevice.peersRating[secondDeviceIndex] * -1000000 + secondDevice.chunksCount * 1000 + secondDevice.id;
            return firstDeviceScore - secondDeviceScore;
        });

        if (emittingDevice.incomingRequests[0]) {
            const [chunkIndex, recipientDeviceIndex] = emittingDevice.incomingRequests[0];
            responseQueue.push([chunkIndex, recipientDeviceIndex, emittingDevice.id]);
        }

        emittingDevice.incomingRequests = [];
    }

    for (let r = 0; r < responseQueue.length; ++r) {
        const [chunkIndex, recipientDeviceIndex, emittingDeviceIndex] = responseQueue[r];

        const recipientDevice = devicesMap.get(recipientDeviceIndex);
        const emittingDevice = devicesMap.get(emittingDeviceIndex);

        ++recipientDevice.chunksCount;
        recipientDevice.chunksArray[chunkIndex] = true;
        ++recipientDevice.peersRating[emittingDevice.id];
        recipientDevice.completed = recipientDevice.chunksCount === totalChunks;
        if (recipientDevice.completed) {
            ++completedDevices;
        }

        const chunk = chunksMap.get(chunkIndex);
        ++chunk.count;
    }
}

let result = '';

for (let d = 1; d < totalDevices; ++d) {
    const device = devicesMap.get(d);
    result += device.slots + ' ';
}

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