Краткий хинт по решению от автора задачи:
Эта задача довольно широко известна, но это не делает ее менее сложной.
Кстати, справились далеко не все ... Так что рассмотрим подробнее.
Торговцу номер 1 нужен товар номер 3 (например), торговцу 3 - товар 8,
торговцу 8 - товар 5 и так далее. Торговцев конечное число, поэтому эта
последовательность рано или поздно зациклится (в ней встретится торговец,
которому нужен товар 1). Таким образом, выделится список торговцев, которые
хотят передать свой товар друг другу по циклу. Разумеется, это, возможно, не
для всех торговцев, среди оставшихся снова проведем ту же процедуру... В
конце концов, все торговцы окажутся разбитыми на циклы разной длины. В
частности, если торговец изначально имеет нужный ему товар, то он в
одиночестве образует цикл длины 1. Если двум торговцам нужно просто
поменяться между собой, то они образуют цикл длины 2 - эти обмены выполняются
в первый же день.
В примере, приведенном в задаче, торговцы 1 и 2 образуют цикл длины 2 (они
меняются в первый же день, и дальше просто не участвуют в обменах), торговец
3 образует цикл длины 1 и просто никак не проявляет себя, а торговцы 4, 5, 6,
7 образуют цикл длины 4, который удается организовать за два дня.
Докажем, что любой цикл можно организовать за два дня. В самом деле, пусть у
нас есть цикл произвольной длины n. Нарисуем мысленно правильный n-угольник и
расставим торговцев у его вершин в порядке их следования в цикле. Тогда то,
что нам нужно сделать, на геометрическом языке называется "поворот вокруг
центра многоугольника на угол 2PI/n.
Посмотреть решение на языке C: Решение Алексея Данченко
Посмотреть решение на языке Pascal: Решение Александра Науменко
|