Advertisement
Guest User

2048

a guest
Jan 24th, 2020
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define sz(x) int(x.size())
  4. #define pb push_back
  5. #define FER(i,a,b) for(ll i = ll(a); i < ll(b); ++ i)
  6. #define IFR(i,a,b) for(ll i = ll(a); i >= ll(b); -- i)
  7. #define all(v) (v).begin(),(v).end()
  8. #define mp make_pair
  9. #define ff first
  10. #define ss second
  11. #define fill(x,v) memset(x,v,sizeof(x))
  12. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  13. #define sqr(x) (x)*(x)
  14. #define bas 987625403
  15. #define N 100010
  16. typedef long double ld;
  17. typedef long long ll;
  18. typedef pair<ll,ll> ii;
  19.  
  20. template<class T> ostream & operator<<(ostream&out, vector<T> & v){
  21.     out<<"[";
  22.     for(auto k : v)out<<k<<" ";
  23.     out<<"]";
  24.     return out;
  25. }
  26.  
  27. int n,k, flag;
  28. ld p;
  29. map< pair<int,vector<int>>, ld > dp;
  30.  
  31. bool border(vector<int> &vec){
  32.     for(int x : vec) if(x > 1) return false;
  33.     return true;
  34. }
  35.  
  36. vector<int> getNext(vector<int> vec){
  37.     for(int i = k-1; i >= 0; --i){
  38.         if(i+1 < k) vec[i+1] += vec[i]/2;
  39.         vec[i] = (vec[i]+1)/2;
  40.     }
  41.     return vec;
  42. }
  43.  
  44. int sum(vector<int> &vec){
  45.     int ans = 0;
  46.     for(int x : vec) ans += x;
  47.     return ans;
  48. }
  49.  
  50. ld Init(){
  51.     if(flag == 0) return 1e100;
  52.     return 0;
  53. }
  54.  
  55. ld Op(ld a, ld b){
  56.     if(flag == 0) return min(a,b);
  57.     return max(a,b);
  58. }
  59.  
  60. ld go(pair<int,vector<int>> par){
  61.     //cout << par.second << " pos = " << par.first << endl;
  62.     if(dp.count(par)) return dp[par];
  63.     if(sum(par.second) == 1) return dp[par] = 1;
  64.     if(border(par.second)){
  65.         int pos = par.first, cnt = 0, ptr = -1;
  66.         for(int i = pos-1; i >= 0; --i){
  67.             cnt += par.second[i];
  68.             if(par.second[i]) ptr = i;
  69.         }
  70.         if(ptr == -1){
  71.             for(int i = pos+1; i < k; ++i){
  72.                 if(par.second[i]){
  73.                     ptr = i;
  74.                     cnt++;
  75.                     break;
  76.                 }
  77.             }
  78.         }
  79.         assert(ptr != -1);
  80.         vector<int> vec = par.second;
  81.         ld ans = 0;
  82.         if(cnt == 1){
  83.             // juega y gana
  84.             ld ans = 0;
  85.             vec[ptr]--;
  86.             if(ptr+1 < k) vec[ptr+1]++;
  87.             ans += p*go(mp(pos,vec));
  88.             // juega y pierde
  89.             vec[ptr]++;
  90.             if(ptr+1 < k) vec[ptr+1]--;
  91.             if(pos+1 < k){
  92.                 vec[pos]--;
  93.                 vec[pos+1]++;
  94.                 ans += (1-p)*go(mp(pos+1,vec));
  95.             }
  96.             return dp[par] = ans;
  97.         }else{
  98.             int p1 = 0;
  99.             while(vec[p1] == 0) p1++;
  100.             int p2 = p1+1;
  101.             while(vec[p2] == 0) p2++;
  102.             ans = Init();
  103.             // gana p1
  104.             vec[p2]--;
  105.             vec[p2+1]++;
  106.             ans = Op(ans,go(mp(pos,vec)));
  107.             vec[p2]++;
  108.             vec[p2+1]--;
  109.             // gana p2
  110.             vec[p1]--;
  111.             vec[p1+1]++;
  112.             ans = Op(ans,go(mp(pos,vec)));
  113.             return dp[par] = ans;
  114.         }
  115.     }
  116.     vector<int> nxt = getNext(par.second);
  117.     int pos = par.first;
  118.     int x = par.second[pos];
  119.     if(x == 1){
  120.         return dp[par] = go(mp(pos,nxt));
  121.     }else if(x % 2 == 0){
  122.         ld ans1 = go(mp(pos,nxt)) * p;
  123.         ld ans2 = 0;
  124.         if(pos+1 < k) ans2 = go(mp(pos+1,nxt)) * (1-p);
  125.         return dp[par] = ans1 + ans2;
  126.     }else{
  127.         ld ans = 0;
  128.         // juegas y ganas
  129.         ans += ld(x-1)/x * p * go(mp(pos,nxt));
  130.         // juegas y pierdes
  131.         if(pos+1 < k) ans += ld(x-1)/x * (1-p) * go(mp(pos+1,nxt));
  132.         // no juegas
  133.         ans += ld(1)/x * go(mp(pos,nxt));
  134.         return dp[par] = ans;
  135.     }
  136.     assert(false);
  137. }
  138.  
  139. int main(){
  140.    
  141.     fastio;
  142.     flag = 0;
  143.     cin >> n >> k >> p;
  144.     vector<int> vec(k,0);
  145.     vec[0] = n;
  146.     cout << fixed << setprecision(10) << go(mp(0,vec)) << " ";
  147.     flag = 1;
  148.     dp.clear();
  149.     cout << fixed << setprecision(10) << go(mp(0,vec)) << endl;
  150.  
  151.     return 0;
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement