Плохой Санта

Рассмотрим задачу отдельно для хороших и плохих детей. Для удобства разобьём детей на четыре группы:

1. Дети, у которых должен смениться даритель.
2. Дети, у которых должен смениться получатель.
3. Дети, у которых должны смениться и даритель, и получатель.
4. Дети, у которых ничего не должно измениться.

Теперь рассмотрим два случая.

Случай 1. В третьей группе есть как минимум два ребёнка. В этом случае мы можем объединить этих детей в цикл: первый ребёнок дарит подарок второму, второй — третьему, и так далее, а последний дарит подарок первому.

Случай 2. В третьей группе только один ребёнок. Задача в этом случае делится на два подслучая:

1. Если в первой и второй группах есть хотя бы один ребёнок:
   - Берём одного ребёнка из второй группы и меняем ему получателя на ребёнка из третьей группы.
   - Ребёнка из первой группы делаем получателем подарка от ребёнка из третьей группы.

2. Если первая и вторая группы пусты:
   - Выбираем любого ребёнка из четвёртой группы и меняем его получателя на ребёнка из третьей группы.
   - Ребёнку, которому ранее дарил подарок выбранный из четвёртой группы ребёнок, назначаем дарителем ребёнка из третьей группы.

После этого остаются дети из первой и второй групп. Для каждого ребёнка из второй группы меняем получателя на ребёнка из первой группы.