Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
227. Странная игра
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 02/07/2007 | Лето 2007 дорешивание ( 5E) |
| 11/07/2007 | Лето 2007 - 5 (E) |
| 09/12/2010 | Сборы: Общий итог (4C) |
| 30/12/2010 | Сборы 4: Практика (C) |
| 30/12/2010 | Сборы 4: Домашнее задание (C) |
| 28/10/2014 | Занятие 9 (A) |
| 03/07/2019 | Лето 2019 - 2 (E) |
Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
