Ujjawaldx

Untitled

Jan 1st, 2015
281
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int bit[100];
  4. int bitcheck(long long int num,int lim)
  5. {
  6.     fill(bit,bit+100,0);
  7.     int i=0;
  8.     while(num!=0)
  9.     {
  10.         bit[i++]=num%2;
  11.         num/=2;
  12.     }
  13.  
  14.     int dp[100];
  15.     fill(dp,dp+100,0);
  16.     if(bit[0]==1)  dp[0]=1;
  17.     else dp[0]=0;
  18.     //cout<<"bot ";
  19.     for(int k=1;k<=60;k++){
  20.         //cout<<bit[k]<<" ";
  21.         if(bit[k]==1 && bit[k-1]==1) dp[k]=dp[k-1]+1;
  22.         else if (bit[k]==1 && bit[k-1]==0) dp[k]=1;
  23.         else
  24.            dp[k]=0;
  25.     }
  26.     //cout<<endl;
  27.     int max=0;
  28.     for(int p=0;p<i;p++)
  29.     {
  30.         //cout<<dp[p]<<" ";
  31.         if(dp[p]>=max) max=dp[p];
  32.     }
  33.     //cout<<endl;
  34.     if(max>=lim) return 1;
  35.     else
  36.      return 0;
  37. }
  38. int main() {
  39.     int n,k;
  40.     cin>>n>>k;
  41.     long long int count=0;
  42.     long long int s=pow(2,n);
  43.     for(long long int i=0;i<s;i++)
  44.     {
  45.         int res=bitcheck(i,k);
  46.         //cout<<"res "<<res<<endl;
  47.         if(res)  count++;
  48.        
  49.     }
  50.     long long int gcd1=__gcd(count,s);
  51.     cout<<count/gcd1<<"/"<<s/gcd1;
  52.     // your code goes here
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment