Подразделы

Дата и время

01/11/2024 04:57:33

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЛето 5

printE. Странная игра

Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Витя играет сам с собой в странную игру: он задумывает целые числа `N\ (2\ ≤\ N\ ≤\ 100000)`, `a` и `b\ (0\ ≤\ a,b\ <\ N)`. После этого, отправляясь от числа `a`, он хочет получить число `b` за наименьшее число ходов. За один ход разрешается от числа `x` перейти к одному из чисел `(x\ +\ 1)\ mod\ N,\ (x^2+1)\ mod\ N` или `(x^3+1)\ mod\ N`. Ваша задача: написать программу, которая определяет искомое наименьшее число ходов и последовательность чисел, которые при этом получаются (включая начальное `a` и конечное `b`).
В первой строке входного файла записаны целые числа `N,\ a` и `b`.
Если не существует способа получить число `b` из числа `a` указанным в условии способом, то в первой строке вывести число `-1`.
В противном случае в ней должно быть искомое наименьшее число ходов `L`. В этом случае во второй строке должна быть выведена последовательность `a=a_0,\ a_1,\ …,\ a_L=b` чисел в том порядке, в котором они получаются в процессе преобразования.

Пример ввода

7 5 2

Пример вывода

2
5 6 2
Источник: http://neerc.ifmo.ru/school/archive/
loading