fork download
copy 
  1. #include <iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4.  
  5. #define MAX 1000000001
  6. #define gc getchar_unlocked
  7.  
  8. inline int inp(){
  9. 	int n=0;
  10. 	char c;
  11. 	c=gc();
  12. 	while(c<'0' && c>'9'){
  13. 		c=gc();
  14. 	}
  15. 	while(c>='0' && c<='9'){
  16. 		n=(n<<3)+(n<<1)+c-'0';
  17. 		c=gc();
  18. 	}
  19. 	return n;
  20. }
  21.  
  22. int ar[45]={0};
  23. int f=0;
  24.  
  25. void precompute()
  26. {
  27. int i;
  28. ar[0]=0;
  29. ar[1]=1;
  30. ar[2]=2;
  31.  for(i=3;i<=44 ; i++)
  32.     {
  33.     ar[i]=ar[i-1]+ar[i-2];
  34.  
  35.     //cout<<ar[i]<<" ";
  36.     }
  37. }
  38.  
  39. int bin_search(int x)   // 1 2 3 5 8 13 21 34
  40. {
  41. int low=0, high=44, mid;
  42.  while(low<=high)
  43.  {
  44.  mid=(low+high)/2;
  45.  if(ar[mid]==x)
  46.   {
  47.   f=1;
  48.   return (mid-1);
  49.   }
  50.  else if(ar[mid]<x)
  51.  {
  52.  if(ar[mid]<x && ar[mid+1]>x)
  53.  {
  54.   f=2;
  55.   return mid;
  56.  }
  57.  else
  58.   low=mid+1;
  59.  }
  60.  else if(ar[mid]>x)
  61.  {
  62.   if(ar[mid]>x && ar[mid-1]<x)
  63.   {
  64.   f=2;
  65.    return mid-1;
  66.   }
  67.   else
  68.    high = mid-1;
  69.  }
  70.  }
  71. }
  72.  
  73.  
  74. int main() {
  75. 	// your code goes here
  76. 	precompute();
  77. 	int test;
  78.  
  79. 	test=inp();
  80. 	while(test--)
  81. 	{
  82. 	int i,n,c,pos,t,k;
  83.  
  84.     n=inp();
  85.     int sum=0;
  86.     pos=bin_search(n);
  87.     //cout<< "pos is "<<pos<<endl;
  88.     if(f==1)
  89.     {
  90.     printf("1");
  91.     for(i=1;i<pos;i++)
  92.      printf("0");
  93.     }
  94.     else if(f==2)
  95.     {
  96.     printf("10");
  97.     sum=ar[pos];
  98.     c=sum;
  99.     k=pos-2;
  100.     int inc=0;
  101.     while(k>0)
  102.     {
  103.       sum +=ar[k];
  104.       if(sum>n)
  105.        {
  106.        sum =c;
  107.        printf("0");
  108.        }
  109.        else if(sum<n)
  110.        {
  111.        inc=1;
  112.        c=sum;
  113.        printf("1");
  114.        }
  115.        else if(sum==n)
  116.        {
  117.        printf("1");
  118.        t=k;
  119.        break;
  120.        }
  121.        k= k-1-inc;
  122.        if(inc == 1)
  123.         printf("0");
  124.        inc=0;
  125.       //cout<<"k is and sum is "<<k<<" "<<sum<<endl;
  126.      }
  127.     }
  128.     //cout<<"t is "<<t<<endl;
  129.      if(t!=1)
  130.      {
  131.       for(i=t-1;i>=1;i--)
  132.        printf("0");
  133.      }
  134.  
  135.     printf("\n");
  136.     }
  137. 	return 0;
  138. }
Success #stdin #stdout 0s 2688KB
comments (?)
stdin
copy 
100
300
301
302
303
304
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
30
1000000000
10000000
10000000
10000000
9999999
8888
777
999
10000000
999999
stdout
copy 
100100010101
100100100000
100100100001
100100100010
100100100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
1010000100100001010101000001000101000101001
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100100
1000001010010010100001000000100010
1001001010000001000
10010001000010
100000000010101
1000001010010010100001000000100100
10001010000000000010010101010
1010001
https://ideone.com/ibCNbn
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!