竞赛基础算法

【题目描述】九连环（ring）

九连环是一种源于中国的传统智力游戏，有九个金属环套在上方一个由金属丝做成的环杆上，并且互相牵连。九个环从左到右依次为l～9，每个环有两种状态：1和0，1表示环在杆上，0表示环不在杆上。初始状态是九个环都在杆上，即：111111111，目标状态是九个环都不在杆上，即：000000000，图2.23的状态为110000000，由初始状态到目标状态的变化规则是：

（1）第一只环为无论何时均可自由上下横行；

（2）第二只环只有在第一环为1时，才能自由上下；

（3）想要改变第n（n＞2）个环的状态，需要先使第一到第（n－2）环均为下杆，且第n－1个环为上杆，而与第n＋l个到第九环状态无关；

（4）每改变一个环，记为一步。

图2.23

 

现在九连环由111111111变到000000000，求中间第i步的状态。

【输入格式】

输入有若干行，每行一个整数i。

【输出格式】

输出若干行，每行仅包含中间第i步的状态。如果输入的步数大于实际变换所需的步数，则输出-1。

【输入样例】

2

500

【输出样例】

010111111

-1