找妹子

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

    言荣同学参加了11月的找妹子活动。在市常委,党支部领导的亲切关怀下,校团委每天为他安排一个妹子约会(从12月1日到12月31日)。言荣同学发现这31个妹子都很不错,所以决定同时和她们交往(就是脚踏许多只船的意思)。可是当他和有些妹子同时交往时,这些妹子会吵架。处理这些妹子争吵会让言荣同学的心情变糟。所以言荣同学决定尝试每种搭配妹子的组合,以找到使他心情最好的妹子组合。
    为了更好地解释言荣同学的方法,我们来看看当只有3个妹子时言荣同学是怎么做的。1表示追,0表示甩。
Day Girl
0   000
1   001
2   010
3   011
4   100
5   101
6   110
7   111
    也就是说言荣同学会用2^3-1天尝试2^3种搭配妹子的方法。因为他本来就是光棍所以第0天的状态不用尝试。那么问题来了,有的时候言荣同学需要同时改变他与很多妹子的关系(比如从第3天到第4天就要改变他和所有妹子的关系)。同时改变很多他和妹子的关系是一个多么浩大的工程啊!

    因此他找到一个巧妙的方法,每天只需要改变他与一个妹子的关系,并且在2^n-1天后尝试完所有的妹子组合。
    当n=2时,合法的方法是:
Day Girl
0   00
1   01
2   11
3   10

    当n=3时,可能你已经想到了合法的方法。就是把n=2的情况照搬下来,然后镜面对称一下,翻折下去的部分前面加上个1。
Day Girl
0   000
1   001
2   011
3   010
--------
4   110
5   111
6   101
7   100
    言荣同学用这种方法尝试了31个妹子交往所有的妹子组合。不幸的是他只记得自己第m天心情最好,但是忘了那一天是和哪些妹子在一起了。

Input

    多组测试数据,每组测试数据包含一个自然数m,表示第m天。0 <= m <= 2^31-1
    测试数据不会多于10^5组

Output

    31位长的二进制数,表示言荣同学那一天和哪些妹子在一起

Sample Input

1
2
3
4
5
6
7

Sample Output

0000000000000000000000000000001
0000000000000000000000000000011
0000000000000000000000000000010
0000000000000000000000000000110
0000000000000000000000000000111
0000000000000000000000000000101
0000000000000000000000000000100

Source

Liaojingyi

Manager

Information
Solved Number42
Submit Number70
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel