九连环
成绩 | 100 | 开启时间 | 2020年06月13日 星期六 10:10 |
折扣 | 0.8 | 折扣时间 | 2020年06月13日 星期六 10:10 |
允许迟交 | 是 | 关闭时间 | 2020年06月13日 星期六 10:10 |
输入文件 | ring.in | 输出文件 | ring.out |
题目描述
九连环是由九个彼此套接的圆环和一根横杆组成,九个环从左到右依次为l~9,每个环有两种状 态:1和0,1表示环在杆上,0表示环不在杆上。初始状态是九个环都在杆上,即:111111111,目标状态是九个环都不在杆上,即:000000000,由初始状态到目标状态的变化规则是:
(1)第一环为无论何时均可自由上下横行;
(2)第二只环只有在第一环为1时,才能自由上下;
(3)想要改变第n(n>2)个环的状态,需要先使第一到第(n-2)环均为下杆,且第n-1个环为上杆,而与第n+l个到第九环状态无关;
(4)每改变一个环,记为一步。
现在九连环由111111111变到000000000,求中间第i步的状态。
输入
若干行,每行一个整数i
输出
若干行,每行仅包含中间第i步的状态。如果输入的步数大于实际变换所需的步数,则输出-1。
样例输入
2
5000
样例输出
010111111
-1