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

@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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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";
    }
}

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .

@toder 0 / 0 / 0 Регистрация: 29.12.2021 Сообщений: 14

	Новые требования 21.04.2022, 22:37. Показов 1268. Ответов 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

Опции темы