jakaria_hossain

lightoj - 1042 - Secret Origins

Aug 9th, 2019
105
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