Новые требования

@toder · Регистрация: 29.12.2021

Студворк — интернет-сервис помощи студентам

В институте N студентов и N компьютеров. В институте вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого студента будут определены ровно К компьютеров, к которым этот студент будет иметь допуск (т. е. за которыми этот студент будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно К студент. Информация о том, какой студент к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу компьютерных классов, студенты должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков студентов найдёт рассадку студентов по компьютерам, удовлетворяющую этим допускам.
Из общих соображений секретности известно лишь, что К будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений К.

Формат входных данных
В первой строке входного файла записаны натуральные числа N и К (1≤N≤ 500). Далее следуют K×N строк, в каждой из которых записаны два натуральных числа — номер студента и номер компьютера, к которому этот
студент имеет допуск. Гарантируется, что каждый студент имеет допуск ровно к К компьютерам, что к каждому компьютеру ровно К студентов имеют допуск, и что K равно либо 1, либо 2, либо 4.

Формат выходных данных
В выходной файл выведите N строк, в каждой по два числа — номер студента и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке. Если есть несколько решений, выведите любое. Можно доказать, что для любого входного файла, удовлетворяющего указанным ограничениям, всегда имеется как минимум одно решение.

Примеры
input.txt
3 1
2 3
3 1
1 2
output.txt
3 1
1 2
2 3

@igorrr37 · 22.04.2022, 07:09

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
 
 
struct comp
{
    int c{};
    std::vector<int> v;
};
 
int main()
{
    std::stringstream ss
    {
        "3 1 2 3 3 1 1 2"
        //"6 3 1 1 2 1 3 1 4 2 5 2 6 2 1 3 2 3 4 3 3 4 5 4 6 4 1 5 2 5 4 5 3 6 5 6 6 6"
    };
    int n{}, k{};
    ss >> n >> k;
    std::vector<comp> vct(n);
    int s{}, c{};
    for (int i = 0; i < n * k; ++i)
    {
        ss >> s >> c;
        vct[c - 1].c = c;
        vct[c - 1].v.push_back(s);
    }
    /*
    for (auto const& [c, v] : mp)
    {
        std::cout << c << " ";
        for (auto n : v)
        {
            std::cout << n << " ";
        }
        std::cout << "\n";
    }
    */
    std::vector<std::pair<int, int>> vres;
    while (true)
    {
        auto imin = std::min_element(vct.begin(), vct.end(), [](auto const& a, auto const& b) {return a.v.size() < b.v.size(); });
        if (imin == vct.end())
            break;
        vres.emplace_back(imin->c, imin->v[0]);
        s = imin->v[0];
        vct.erase(imin);
        for (auto& [c, v] : vct)
        {
            if (auto it = std::find(v.begin(), v.end(), s); it != v.end())
            {
                v.erase(it);
            }
        }
    }
    for (auto const& [c, s] : vres)
    {
        std::cout << s << " " << c << "\n";
    }
}

@toder 0 / 0 / 0 Регистрация: 29.12.2021 Сообщений: 14
		1
	Новые требования 21.04.2022, 22:37. Показов 780. Ответов 1 Метки c++ (Все метки) В институте N студентов и N компьютеров. В институте вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого студента будут определены ровно К компьютеров, к которым этот студент будет иметь допуск (т. е. за которыми этот студент будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно К студент. Информация о том, какой студент к какому компьютеру будет иметь допуск, будет известна лишь непосредственно перед вступлением новых требований в силу. Таким образом, чтобы не прерывать работу компьютерных классов, студенты должны будут быстро решить, кто за каким компьютером будет работать. Для этого им необходимо заранее написать программу, которая по любому распределению допусков студентов найдёт рассадку студентов по компьютерам, удовлетворяющую этим допускам. Из общих соображений секретности известно лишь, что К будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений К. Формат входных данных В первой строке входного файла записаны натуральные числа N и К (1≤N≤ 500). Далее следуют K×N строк, в каждой из которых записаны два натуральных числа — номер студента и номер компьютера, к которому этот студент имеет допуск. Гарантируется, что каждый студент имеет допуск ровно к К компьютерам, что к каждому компьютеру ровно К студентов имеют допуск, и что K равно либо 1, либо 2, либо 4. Формат выходных данных В выходной файл выведите N строк, в каждой по два числа — номер студента и номер компьютера, за которым он должен работать. Строки можно выводить в произвольном порядке. Если есть несколько решений, выведите любое. Можно доказать, что для любого входного файла, удовлетворяющего указанным ограничениям, всегда имеется как минимум одно решение. Примеры input.txt 3 1 2 3 3 1 1 2 output.txt 3 1 1 2 2 3 0

Опции темы