Танцуют все!
(Время: 1 сек. Память: 16 Мб Сложность: 47%)
На вечеринку приглашены N мальчиков и M девочек. Каждый мальчик хочет станцевать с каждой девочкой, а каждая девочка – с каждым мальчиком. Можно организовать несколько раундов. В каждом раунде может танцевать несколько пар так, что каждая пара состоит из одного мальчика и одной девочки.
Требуется организовать минимально возможное число раундов, в результате которых каждый мальчик станцует с каждой девочкой и наоборот, каждая девочка – с каждым мальчиком. При этом никакая пара не должна танцевать дважды и, разумеется, никто не может танцевать дважды в одном раунде.
Входные данные
Входной файл INPUT.TXT содержит два натуральных числа N и M – количество мальчиков и девочек (N ≤ 100, M ≤ 100).
Выходные данные
В первой строке выходного файла OUTPUT.TXT выведите целое число K – минимальное количество раундов. В последующих K строках следует вывести информацию о танцах: в отдельной строке выводится информация о каждом раунде. Раунд описывается целым числом T – количество танцующих пар, после чего идет описание T пар, разделенных пробелом. Информация о паре имеет вид «A-B», где A – номер мальчика, а B – номер девочки. Все мальчики пронумерованы от 1 до N, а девочки – от 1 до M.
Если существует несколько оптимальных решений, то следует вывести любое из них.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 2 2 | 2
2 1-1 2-2
2 1-2 2-1 |
2 | 3 2 | 3
2 1-1 3-2
2 2-2 3-1
2 1-2 2-1 |
Система оценки
Решения, работающие только при N+M ≤ 6, будут оцениваться в 25 баллов.
Решения, работающие только при N=M, будут оцениваться в 30 баллов.
Решения, работающие только для взаимно простых N и M, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|