USER
Напомним, что Зиниум — это шахматная доска размером
n
×
n
n×n клеток. Клетка в левом нижнем её углу имеет координаты
(
1
,
1
)
(1,1), а клетка в правом верхнем углу — координаты
(
n
,
n
)
(n,n). По легенде, если на доске расставить
n
n ферзей таким образом, что ни один из них не будет атаковать другого, то освобождённая энергия Зиниума изменит мир до неузнаваемости. Реки повернутся вспять, небо упадёт на землю, люди научатся называть вещи своими именами…
Все верили в легенду про Зиниум, пока артефакт не попал в руки к Игорю. Когда Игорю удалось расставить
n
n ферзей требуемым образом, ничего не произошло (во всяком случае, Игорь не заметил ничего необычного). Тогда Игорь предположил, что в легенде говорилось не об обычной, а о торической шахматной доске. Чтобы получить торическую шахматную доску размера
n
×
n
n×n, нужно взять обычную доску такого же размера, после чего склеить её верхнюю горизонталь с нижней, а левую вертикаль с правой. На рисунке показано, какие клетки торической шахматной доски
8
×
8
8×8 держит под боем один ферзь. Чтобы проверить свою гипотезу, Игорь пытается расставить на торической доске
n
n ферзей так, чтобы ни один из них не атаковал другого. Помогите ему в этом.
Исходные данные
В единственной строке записано целое число
n
n
(
4
≤
n
≤
1
0
5
)
(4≤n≤10
5
).
Результат
Если искомая расстановка существует, выведите в первой строке «Yes», а во второй —
n
n целых чисел.
i
i-е число должно равняться
y
y-координате ферзя,
x
x-координата которого равна
i
i. Если возможных расстановок несколько, выведите любую из них. Если расстановки не существует, в единственной строке выведите «No».
Sample Tests:
Input Output
1:
5
Yes
2 4 1 3 5
2:
8
No
Step-by-step Solution
[1]
На данной доске ферзь бьёт полностью одну горизонталь, одну вертикаль, а так же по одной диагонали \((x_i + y_i) \% n\) и \((x_i - y_i) \% n\).
Заметим, что если \(n \% 2 = 0\), то сумма всех \((x_i + y_i) \% n\) по модулю \(n\) равна сумме перестановки от 0 до (n - 1), равно \(\frac{n(n-1)}{2} \% n\), но так же сумма всех \((x_i + y_i) \% n\) равна \((\sum x_i + y_i) \% n = n(n-1) \% n = 0\), но \(\frac{n(n-1)}{2} \% n \neq 0\), так как \(\frac{n}{2}\) не делится на \(n\), а \((n-1)\) взаимопросто с \(n\). Значит \(n \% 2 \neq 0\).
Так же рассмотрим \(n \% 3 = 0\). Тогда \((\sum x_i^2 + \sum y_i^2) \% n = \frac{n(n+1)(2n+1)}{3} \% n\). Тогда оно должно быть равно \((\sum (x_i + y_i)^2 + \sum (x_i - y_i)^2) \% n = (2\sum x_i^2 + 2\sum y_i^2) \% n = 2(\sum x_i^2 + \sum y_i^2) \% n = \frac{2n(n+1)(2n+1)}{3} \% n\). Так как \(n \% 3 = 0\) значит \(\frac{2n(n+1)(2n+1)}{3} \% n \neq \frac{n(n+1)(2n+1)}{3} \% n\). Таким образом \(n \% 3 \neq 0\).
Для остальных случаев будем действовать следующим алгоритмом. Начнём с клетки \((1,1)\) и далее будем двигаться по клеткам \((i, (2i - 1) \% n)\). Так как \(n \% 2 \neq 0\), то \((2i - 1) \% n\) пройдёт по всем \(y\). При этом \((3i - 1) \%n\) так же пройдёт по всем различным значениям без повторений так как \(n \% 3 \neq 0\).
Таким образом если \(n \% 2 = 0\) или \(n \% 3 = 0\) ответа не существует.
Иначе расположим ферзей на клетки \((i, (2i - 1) \% n)\).
проверь правильно ли описано решение и если нет, то укажи, где допущена ошибкаASSISTANT
Давайте разберёмся с решением задачи по шагам и подтвердим его корректность.
### Условия задачи
Необходимо разместить на торической шахматной доске размером \( n \times n \) по одному ферзю в каждой колонке так, чтобы ни один ферзь не атаковал другого. На торической доске ферзь атакует:
1. Всё по горизонтали и вертикали (как на обычной шахматной доске).
2. По двум диагоналям, учитывая цикличность доски:
- Диагональ с фиксированной суммой координат \((x_i + y_i) \% n\).
- Диагональ с фиксированной разностью координат \((x_i - y_i) \% n\).
### Анализ шага за шагом
1. **Условие необходимости нечетности и невзаимной делимости на 3:**
- **Чётность (\(n \% 2 = 0\))**:
- Если \(n\) чётно, сумма \((x_i + y_i) \% n\) должна равняться \(\frac{n(n-1)}{2} \% n\), что не равно 0 (поскольку \(\frac{n}{2}\) не делится на \(n\) при чётности). Это приводит к противоречию, поэтому \(n\) не должно быть чётным.
- **Делимость на 3 (\(n \% 3 = 0\))**:
- Аналогично, если \(n\) делится на 3, сумма \((x_i + y_i)^2\) и \((x_i - y_i)^2\) приводит к несоответствию по модулю \(n\), что также делает невозможным размещение ферзей без атак.
**Вывод:** Если \(n\) делится на 2 или на 3, расстановка ферзей невозможна.
2. **Алгоритм построения расстановки при \(n\) не делится на 2 и на 3:**
- Предлагается разместить ферзей на клетках \((i, (2i - 1) \% n)\) для каждого \(i\) от 1 до \(n\).
- **Почему это работает?**
- Поскольку \(n\) нечётно и не делится на 3, выражение \(2i - 1\) по модулю \(n\) покрывает все возможные значения \(y\)-координат без повторений.
- Диагонали \((x_i + y_i) \% n = (i + (2i - 1)) \% n = 3i - 1 \% n\) также будут уникальными, так как \(n\) и 3 взаимно просты.
- Аналогично, диагонали \((x_i - y_i) \% n = (i - (2i - 1)) \% n = -i + 1 \% n\) также будут уникальными.
3. **Проверка на примере:**
- **Для \(n = 5\):**
- Расстановка по формуле \((2i - 1) \% 5\) даст: \([1, 3, 0, 2, 4]\). Переходя к 1-индексации, получаем \([1, 3, 5, 2, 4]\), что соответствует одному из возможных решений.
- **Для \(n = 8\):**
- \(n\) делится на 2, значит решение не существует, что согласуется с примером.
### Заключение
Решение полностью корректно. Оно опирается на известные свойства торической шахматной доски и правильно использует условия делимости \(n\) для определения существования решения. Алгоритм построения расстановки ферзей верен и обеспечивает уникальность строк и диагоналей при заданных условиях.
**Ответ:**
Решение полностью корректно и правильно описывает условия существования расстановки ферзей на торической шахматной доске.