Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2281. Золотая система счисления
Специальные системы счисленияОлимпиадные задачи на русском языке
| 02/04/2016 | Открытые командные соревнования по спортивному программированию "PRIME TIME" ( 6) |
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
C-3PO не слишком силен в математике, но иногда ему нужно хранить в памяти некоторые числовые данные.
Чтобы не быть похожим на R2-D2, который использует заурядное двоичное представление чисел, C-3PO решил
использовать в качестве основания системы счисления отношение золотого сечения `Phi`, равное `(1+sqrt(5))/2`,
свойства которого намекают на его иррациональное мышление и на его золотой корпус.
Любое натуральное число можно представить в виде суммы положительных и отрицательных степеней числа `Phi`, где каждая
степень используется не более одного раза. Например, `1=Phi^0`, `2=Phi^0+Phi^{-1}+Phi^{-2}=Phi^1+Phi^{-2}`,
`3=Phi^1+Phi^0+Phi^{-2}=Phi^2+Phi^{-2}`. Для упрощения запоминания C-3PO желает найти
вариант представления с минимальным числом слагаемых.
Формат ввода
Первая строка ввода одно целое число `N` (`1\ ≤\ N\ ≤\ 10^{18}`) – значение, которое нужно
представить в золотой системе счисления.
Формат вывода
В первой строке вывести одно целое число – минимальное количество слагаемых в
золотом представлении числа `N`. Во второй строке вывести использованные
в представлении степени в порядке убывания.
Пример ввода
3
Пример вывода
2 2 -2
