## Дата и время

02/03/2024 11:49:05

## Авторизация

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

# 1416. Fibary

## Fibary

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

We are familiar with radix number representations where digits read from right-to-left (least significant to most significant) signify increasing powers of some radix (i.e. base) number, e.g. 10^0,\ 10^1,\ 10^2,\ 10^3,\ … in decimal representation or 2^0,\ 2^1,\ 2^2,\ 2^3,\ … in binary representation. For example, the binary number 101001 represents
1\ *\ 2^5\ +\ 0\ *\ 2^4\ +\ 1\ *\ 2^3\ +\ 0\ *\ 2^2\ +\ 0\ *\ 2^1\ +\ 1\ *\ 2^0\ =\ 41.
In this problem, we consider a number representation where digits read from right-to-left (least significant to most significant) signify increasing Fibonacci numbers 1, 2, 3, 5, 8, 13, 21, … we'll call them fibary numbers. Each digit of a fibary number is either 0 or 1. For example, the fibary number 101001 represents
1\ *\ 13\ +\ 0\ *\ 8\ +\ 1\ *\ 5\ +\ 0\ *\ 3\ +\ 0\ *\ 2\ +\ 1\ *\ 1\ =\ 19.
While each number has exactly one radix representation without leading zeroes, it can have more than one fibary representation without leading zeroes. For example, the fibary number 11111 also represents
1\ *\ 8\ +\ 1\ *\ 5\ +\ 1\ *\ 3\ +\ 1\ *\ 2\ +\ 1\ *\ 1\ =\ 19.
However, each number has exactly one fibary representation without leading zeroes or successive ones – its canonical fibary representation. Of all the fibary representations of a number, the canonical one is the largest when viewed as a binary number.
Input Format
Each line contains the decimal representation of a nonnegative number less than 2^31.
Output Format
For each decimal number input, output a line containing its canonical fibary representation.

Sample Input

0
19
10
100
1000000000
123456
654321
2009
317810


Sample Output

0
101001
10010
1000010100
1010000100100001010101000001000101000101001
1000000001001001000000000
1001000100000100000000000001
1001000010000001
10101010101010101010101010

Source: California State Polytechnic University Programming Contest, Winter 2009