SHARE
TWEET

lightoj - 1042 - Secret Origins

jakaria_hossain Aug 9th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. int main()
  5. {
  6.     int t,c;
  7.     cin>>t;
  8.     for(c=1; c<=t; c++)
  9.     {
  10.         ll q,x,p,mul=1,z=0;
  11.         cin>>q;
  12.         bool f= false;
  13.         ll ara[70],i=0,ans=0;
  14.         while(q>0)
  15.         {
  16.             ara[i]=q%2;
  17.             if(ara[i]==0)
  18.                 z++;
  19.             i++;
  20.             q/=2;
  21.         }
  22.         q=i;
  23.         if(z==0)
  24.         {
  25.             ara[q-1]=0;
  26.             ara[q]=1;
  27.             q++;
  28.         }
  29.         else
  30.         {
  31.             for(i=0; i<q-1; i++)
  32.             {
  33.                 if(ara[i]==1 && ara[i+1]==0)
  34.                 {
  35.                     x=i;
  36.                     ara[i]=0;
  37.                     ara[i+1]=1;
  38.                     f=true;
  39.                     break;
  40.                 }
  41.             }
  42.             if(f)
  43.             {
  44.                 for(i=0; i<x; i++)
  45.                 {
  46.                     if(ara[i]==1)
  47.                         ans++;
  48.                     ara[i]=0;
  49.                 }
  50.                 for(i=0; i<ans; i++)
  51.                     ara[i]=1;
  52.             }
  53.             else
  54.             {
  55.                 z=0;
  56.                 for(i=q-1;i>=0;i--)
  57.                 {
  58.                     if(ara[i]==1)z++;
  59.                     ara[i]=0;
  60.                 }
  61.                 ara[q++]=1;
  62.                 for(i=0;i<z-1;i++)ara[i]=1;
  63.             }
  64.         }
  65.  
  66.         ans=0;
  67.         //for(i=q-1;i>=0;i--)cout<<ara[i]<<endl;
  68.         for(i=0; i<q; i++)
  69.         {
  70.             ans+=(ara[i]*mul);
  71.             mul*=2;
  72.         }
  73.         cout<< "Case "<<c<< ": "<<ans<<endl;
  74.     }
  75. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top