Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define sz(x) int(x.size())
- #define pb push_back
- #define FER(i,a,b) for(ll i = ll(a); i < ll(b); ++ i)
- #define IFR(i,a,b) for(ll i = ll(a); i >= ll(b); -- i)
- #define all(v) (v).begin(),(v).end()
- #define mp make_pair
- #define ff first
- #define ss second
- #define fill(x,v) memset(x,v,sizeof(x))
- #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
- #define sqr(x) (x)*(x)
- #define bas 987625403
- #define N 100010
- typedef long double ld;
- typedef long long ll;
- typedef pair<ll,ll> ii;
- template<class T> ostream & operator<<(ostream&out, vector<T> & v){
- out<<"[";
- for(auto k : v)out<<k<<" ";
- out<<"]";
- return out;
- }
- int n,k, flag;
- ld p;
- map< pair<int,vector<int>>, ld > dp;
- bool border(vector<int> &vec){
- for(int x : vec) if(x > 1) return false;
- return true;
- }
- vector<int> getNext(vector<int> vec){
- for(int i = k-1; i >= 0; --i){
- if(i+1 < k) vec[i+1] += vec[i]/2;
- vec[i] = (vec[i]+1)/2;
- }
- return vec;
- }
- int sum(vector<int> &vec){
- int ans = 0;
- for(int x : vec) ans += x;
- return ans;
- }
- ld Init(){
- if(flag == 0) return 1e100;
- return 0;
- }
- ld Op(ld a, ld b){
- if(flag == 0) return min(a,b);
- return max(a,b);
- }
- ld go(pair<int,vector<int>> par){
- //cout << par.second << " pos = " << par.first << endl;
- if(dp.count(par)) return dp[par];
- if(sum(par.second) == 1) return dp[par] = 1;
- if(border(par.second)){
- int pos = par.first, cnt = 0, ptr = -1;
- for(int i = pos-1; i >= 0; --i){
- cnt += par.second[i];
- if(par.second[i]) ptr = i;
- }
- if(ptr == -1){
- for(int i = pos+1; i < k; ++i){
- if(par.second[i]){
- ptr = i;
- cnt++;
- break;
- }
- }
- }
- assert(ptr != -1);
- vector<int> vec = par.second;
- ld ans = 0;
- if(cnt == 1){
- // juega y gana
- ld ans = 0;
- vec[ptr]--;
- if(ptr+1 < k) vec[ptr+1]++;
- ans += p*go(mp(pos,vec));
- // juega y pierde
- vec[ptr]++;
- if(ptr+1 < k) vec[ptr+1]--;
- if(pos+1 < k){
- vec[pos]--;
- vec[pos+1]++;
- ans += (1-p)*go(mp(pos+1,vec));
- }
- return dp[par] = ans;
- }else{
- int p1 = 0;
- while(vec[p1] == 0) p1++;
- int p2 = p1+1;
- while(vec[p2] == 0) p2++;
- ans = Init();
- // gana p1
- vec[p2]--;
- vec[p2+1]++;
- ans = Op(ans,go(mp(pos,vec)));
- vec[p2]++;
- vec[p2+1]--;
- // gana p2
- vec[p1]--;
- vec[p1+1]++;
- ans = Op(ans,go(mp(pos,vec)));
- return dp[par] = ans;
- }
- }
- vector<int> nxt = getNext(par.second);
- int pos = par.first;
- int x = par.second[pos];
- if(x == 1){
- return dp[par] = go(mp(pos,nxt));
- }else if(x % 2 == 0){
- ld ans1 = go(mp(pos,nxt)) * p;
- ld ans2 = 0;
- if(pos+1 < k) ans2 = go(mp(pos+1,nxt)) * (1-p);
- return dp[par] = ans1 + ans2;
- }else{
- ld ans = 0;
- // juegas y ganas
- ans += ld(x-1)/x * p * go(mp(pos,nxt));
- // juegas y pierdes
- if(pos+1 < k) ans += ld(x-1)/x * (1-p) * go(mp(pos+1,nxt));
- // no juegas
- ans += ld(1)/x * go(mp(pos,nxt));
- return dp[par] = ans;
- }
- assert(false);
- }
- int main(){
- fastio;
- flag = 0;
- cin >> n >> k >> p;
- vector<int> vec(k,0);
- vec[0] = n;
- cout << fixed << setprecision(10) << go(mp(0,vec)) << " ";
- flag = 1;
- dp.clear();
- cout << fixed << setprecision(10) << go(mp(0,vec)) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement