1. Главная
  2. Библиотека
  3. Менеджмент
  4. Совсем скоро пройдет очередной всекоролевский чемпионат...
Разбор задачи

Совсем скоро пройдет очередной всекоролевский чемпионат по футболу на льду. В чемпионате примут участие N (1

  • Предмет: Менеджмент
  • Автор: Кэмп
  • #Управление проектами
  • #Управление проектами в экономике
Совсем скоро пройдет очередной всекоролевский чемпионат по футболу на льду. В чемпионате примут участие N (1

Условие:

Совсем скоро пройдет очередной всекоролевский чемпионат по футболу на льду. В чемпионате примут участие N (1<=N<=150) команд, из различных городов. Каждый матч будет проходить в городе одной из команд, участвующих во встрече. Всего пройдет M (1<=M<=22350) встреч, для каждой уже известны участники и город, на стадионе которого будет проходить встреча. Известно, что никакая пара команд не встретится на одном стадионе более одного раза. Вам требуется составить расписание встреч, так чтобы турнир закончился за наименьшее число дней и чтобы:
1) не существовало команды, проводящей более одного матча в один день у себя дома;
2) не существовало команды, проводящей более одного матча в один день в гостях.

Решение:

1. Анализ ограничений и постановка задачи

У нас есть MM матчей. Каждый матч kk задан как (Ak,Bk,Ck)(A_k, B_k, C_k), где CkC_k — хозяин.

Ограничения на команду ii в любой день dd:

  1. Команда ii может провести не более одного домашнего матча в день dd.
  2. Команда ii может провести не более одного гостевого матча в день dd.

Мы ищем минимальное QQ такое, что существует назначение дня dk{1,2,,Q}d_k \in \{1, 2, \ldots, Q\} для каждого матча kk, удовлетворяющее этим условиям.

2. Поиск по ответу (Бинарный поиск по QQ)

Минимальное возможное QQ равно 1. Максимальное возможное QQ равно...

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какой метод используется для проверки возможности составления расписания для фиксированного количества дней Q в данной задаче?

Что нужно знать по теме:

Что нужно знать по теме

Алгоритм решения

Топ 3 ошибок

Что спросит препод

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет