include iostream include bitset include string include algorithm using

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>
using namespace std;
int is_pinary(long long n)
{
long long l=0;
while (n)
{
long long r = (1&n);
if (r&&l) return 0;
if (!r && l) l =0;
if (r && !l) l =1;
n>>=1;
}
return 1;
}
int bits[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887,
9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141};
int main()
{
long long n,cases;
scanf("%lld\n",&cases);
while (cases-- && scanf("%lld\n",&n)==1)
{
long long start = n;
long long res=0;
while (n>1)
{
long long i=0;
while (bits[i]<n) i++;
n-=bits[i-1]+1;
i-=2;
res|=(long long)1<<(i);
}
res+=1;
while (!is_pinary(res))
{
res++;
}
bitset<100> a=res;
string ans = a.to_string();
while (ans[0]=='0') ans.erase(0,1);
printf("%s\n",ans.c_str());
//cout << ans << endl;
/*long long wrk=0;
long long count=0;
while (count<start)
{
wrk++;
if (is_pinary(wrk)) count++;
}
a=wrk;
ans = a.to_string();
while (ans[0]=='0') ans.erase(0,1);
cout << ans << endl;*/
}
}