fork download
copy 
  1. /*
  2. ye mera template hai
  3. apna khud likho bc :P
  4. */
  5.  
  6. /*
  7. Author : Sarvagya Agarwal
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12.  
  13. //defines
  14. #define openin freopen("input.txt","r",stdin)
  15. #define openout freopen("output.txt","w",stdout)
  16. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  17. #define ll long long
  18. #define int long long
  19. #define mod 1000000007
  20. #define rep(i,x,y) for (__typeof(x) i=x;i<=y;i++)
  21. #define all(c) (c).begin(),(c).end()
  22. #define ff first
  23. #define ss second
  24. #define pb push_back
  25. #define mp make_pair
  26.  
  27. /* Print pair */
  28. template <typename T,typename S>
  29. ostream & operator << (ostream &os , const pair<T,S> &v) {
  30.     os << "(" ;
  31.     os << v.first << "," << v.second << ")" ;
  32.     return os ;
  33. }
  34. /* Print vector */
  35. template <typename T>
  36. ostream & operator << (ostream &os , const vector<T> &v) {
  37.     os << "[" ;
  38.     int sz = v.size() ;
  39.     for(int i = 0 ; i < sz ; ++i) {
  40.         os << v[i] ;
  41.         if(i!=sz-1)os << "," ;
  42.     }
  43.     os << "]\n" ;
  44.     return os ;
  45. }
  46. /* Print set */
  47. template <typename T>
  48. ostream & operator << (ostream &os , const set<T> &v) {
  49.     T last = *v.rbegin() ;
  50.     os << "[" ;
  51.     for(auto it : v) {
  52.         os << it  ;
  53.         if(it != last) os << "," ;
  54.     }
  55.     os << "]\n" ;
  56.     return os ;
  57. }
  58. /* Print Map */
  59. template <typename T,typename S>
  60. ostream & operator << (ostream &os , const map<T,S> &v) {
  61.     for(auto it : v) {
  62.         os << it.first << " : " << it.second << "\n" ;
  63.     }
  64.     return os ;
  65. }
  66. int power(int a , int b)
  67. {
  68.     int res = 1 ;
  69.     while(b)
  70.     {
  71.         if(b%2) {
  72.             res = (res * a)%mod ;
  73.         }
  74.         b/=2 ;
  75.         a = (a*a)%mod ;
  76.     }
  77.     return res ;
  78. }
  79.  
  80. //debug
  81. #define TRACE
  82.  
  83. #ifdef TRACE
  84. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  85. template <typename Arg1>
  86. void __f(const char* name, Arg1&& arg1){
  87. 		cerr << name << " : " << arg1 << std::endl;
  88. }
  89. template <typename Arg1, typename... Args>
  90. void __f(const char* names, Arg1&& arg1, Args&&... args){
  91. 		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  92. }
  93. #else
  94. #define trace(...)
  95. #endif
  96. int n , k ;
  97. int dp[65][65][65] ;
  98. int solve(int index, int cnt , int max_cnt)
  99. {
  100.     //trace(index,cnt,max_cnt);
  101.     if(index > n) {
  102.         return max_cnt>=k ;
  103.     }
  104.     if(dp[index][cnt][max_cnt] != -1)
  105.         return dp[index][cnt][max_cnt] ;
  106.     int res = 0 ;
  107.     // A
  108.     res += solve(index+1,0,max_cnt) ;
  109.     // B
  110.     res += solve(index+1,cnt+1,max(max_cnt,cnt+1)) ;
  111.     return dp[index][cnt][max_cnt] = res ;
  112. }
  113. int32_t main()
  114. {
  115.     fast;
  116.     memset(dp,-1,sizeof(dp));
  117.     cin >> n >> k ;
  118.     int num = solve(1,0,0) ;
  119.     int den = (1<<n) ;
  120.     int g = __gcd(num,den) ;
  121.     num /= g ;
  122.     den /= g ;
  123.     cout << num << '/' << den << '\n' ;
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0s 5608KB
comments (?)
stdin
copy 
5 1
stdout
copy 
31/32
https://ideone.com/CyiT9S
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!