Камінь-Папір-Ножиці на площині#7322

Камінь-Папір-Ножиці на площині

1 секунда

64 мегабайти

Легка

У цій задачі вам потрібно пройти з одного кута шахівниці в протилежний, дотримуючись певних правил і уникаючи зайвих кроків.

Шахівниця на площині складається з $m$ рядків і $n$ колонок. Кожна клітинка містить один з трьох предметів: камінь, папір або ножиці. Ви починаєте рух з клітинки $(1, 1)$ і прямуєте до $(m, n)$ , виконуючи послідовність ходів. Хід — це переміщення в будь-яку клітинку, що знаходиться не далі ніж на відстані $d$ від поточної. Відстань вимірюється між центрами клітинок: відстань між клітинками $(x_{1}, y_{1})$ (x_1, y_1) і $(x_{2}, y_{2})$ (x_2, y_2) дорівнює $(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}$ \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}. Кожен хід має бути в клітинку, яка містить предмет, що перемагає предмет у попередній клітинці. Як у грі "Камінь-Папір-Ножиці": камінь перемагає ножиці, ножиці перемагають папір, а папір перемагає камінь. Коли ви заходите в клітинку, предмет з неї зникає, тому заборонено відвідувати одну й ту ж клітинку двічі.

Поле досить велике, тому предмети в клітинках визначаються генератором випадкових чисел, а саме лінійним конгруентним генератором. Цей генератор має стан, що є цілим числом $s$ від $0$ до $2^{32} - 1$ 2^{32} - 1. Для отримання наступного випадкового числа від $0$ до $r - 1$ r - 1 виконується присвоєння $s := (s \cdot 1664525 + 1013904223) mod 2^{32}$ s := (s \cdot 1\,664\,525 + 1\,013\,904\,223) \mod 2^{32} і повертається залишок від ділення $s$ на $r$ . Початковий стан $s$ задається на вході.

Предмети в клітинках визначаються наступним чином. Для кожної клітинки генерується випадкове число з множини ${0, 1, 2}$ \{0, 1, 2\} (тобто $r = 3$ r = 3). Якщо це число дорівнює нулю, то в клітинці знаходиться камінь, якщо одиниця — папір, а якщо два — ножиці. Клітинки переглядаються рядок за рядком зверху вниз, клітинки в одному рядку переглядаються зліва направо. Таким чином, порядок обходу клітинок наступний: $(1, 1)$ , $(1, 2)$ , ..., $(1, n)$ , $(2, 1)$ , $(2, 2)$ , ..., $(2, n)$ , ..., $(m, 1)$ , $(m, 2)$ , ..., $(m, n)$ .

Дуже важливо завершити подорож за час, не більше того, за яке можна пройти з клітинки $(1, 1)$ в клітинку $(m, n)$ по прямій зі швидкістю, рівною половині максимальної, плюс три зайвих ходи. Формально кількість ходів не повинна перевищувати дійсне число $\frac{( m - 1 ) ^{2} + ( n - 1 ) ^{2}}{d /2} + 3$ \frac{\sqrt{(m-1)^2 + (n-1)^2}}{d/2} + 3.

За заданими розмірами поля, максимальною довжиною стрибка за один хід і початковим станом випадкового числового генератора знайдіть шлях, що задовольняє всім заданим умовам.

Вхідні дані

Перший рядок містить $m$ , $n$ , $d$ і $s$ : висота і ширина поля, максимальна відстань одного ходу і початковий стан числового генератора ( $100 \leq m, n \leq 2^{16}$ 100 \le m, n \le 2^{16}, $10 \leq d \leq 100$ 10 \le d \le 100, $0 \leq s \leq 2^{32} - 1$ 0 \le s \le 2^{32} - 1). Зверніть увагу, що нижні межі для чисел $m$ , $n$ і $d$ досить великі.

Вихідні дані

У першому рядку виведіть кількість ходів $k$ у знайденому шляху. У наступних $(k + 1)$ (k + 1) рядках виведіть координати відвіданих клітинок у порядку обходу. Спочатку виводьте номер рядка, потім колонки.

Першою клітинкою шляху повинна бути $(1, 1)$ , останньою $(m, n)$ . Кожна клітинка повинна бути відвідана не більше одного разу. Предмет на наступній клітинці повинен перемагати предмет на попередній. Відстань між будь-якими двома послідовними клітинками шляху не повинна перевищувати $d$ , а загальна кількість ходів $k$ не повинна перевищувати дійсного числа $\frac{( m - 1 ) ^{2} + ( n - 1 ) ^{2}}{d /2} + 3$ \frac{\sqrt{(m-1)^2 + (n-1)^2}}{d/2} + 3.

Якщо існує кілька шляхів, виведіть один з них. Гарантовано, що у всіх тестах існує шлях, що задовольняє умовам довжиною не більше $\frac{( m - 1 ) ^{2} + ( n - 1 ) ^{2}}{d /2} + 2$ \frac{\sqrt{(m-1)^2 + (n-1)^2}}{d/2} + 2.

Приклади

Приклад 1

Примітка

Наступна таблиця містить значення $s$ та предмети у відвіданих клітинках заданого прикладу.

Значення дробу дорівнює $3.0959 \dots$ , тому в прикладі слід здійснити не більше дев'яти ходів, а судді формально гарантують існування шляху з семи або менше ходів.