НачалоПодразделы
Другие разделы
| 1437. Котенок Гав и сосиски |
| 1438. Настройка гитары |
| 1439. Древнее сложение |
| 1440. Индикатор загрузки |
| 1441. Нарезка фантиков |
| 1442. Золотая середина |
| 1443. Оригами |
| 1444. Модель Изинга |
Дата и время
20/12/2024 17:15:54
1445. Беговые дорожки
Беговые дорожки
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 24/06/2010 | Лето 2010 дорешивание ( 7I) |
| 07/07/2010 | Лето 2010 - 7 (I) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Между `n` спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется
стадион лишь с `n\ -\ 1` беговой дорожкой, поэтому одновременно могут состязаться только `n\ -\ 1` из `n` участников.
По этой причине соревнования разбиваются на несколько забегов.
Правила соревнований требуют, чтобы каждый из бегунов:
- принимал участие в одинаковом числе забегов,
- бежал на каждой из дорожек одинаковое число раз,
- соревновался с любым из остальных одно и то же число раз.
Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на
соседние дорожки в забеге. При этом у каждого из участников есть не более одного "неприятного" ему конкурента, и
чувство антипатии является взаимным.
Требуется по заданному числу спортсменов, а также списку их антипатий, составить расписание забегов,
удовлетворяющее требованиям организаторов. Гарантируется, что решение существует. При наличии нескольких
решений, допустимо любое из них.
Формат входного файла
В первой строке входного файла находятся целые числа `n\ m`. В следующих `m` строках записаны пары чисел – номера
спортсменов, которых нельзя ставить на соседние дорожки в одном забеге. Спортсмены нумеруются натуральными числами от 1 до `n`.
Формат выходного файла
Первая строка выходного файла должна содержать число забегов `r` в предлагаемой схеме. Следующие `r` строк должны
состоять из `n\ -\ 1` числа – номеров спортсменов, выставляемых на дорожки в каждом из забегов.
Ограничения
`2\ ≤\ n\ ≤\ 100`, `1\ ≤\ r\ ≤\ 1000`.
Пример ввода
4 1 2 3
Пример вывода
4 4 2 1 1 3 4 2 1 3 3 4 2
