ZOJ Problem Set - 2949 Coins of Luck
Chieh
posted @ 2015年8月21日 14:32
in NO Answer No Speak
, 290 阅读
/* Author:Chieh Because Of Coding */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #include <stack> #include <set> #define LL long long #define INF 1e9 #define INF 1e-9 using namespace std; const int maxn=1234; int n; double ai[maxn][maxn]; double bi[maxn][maxn*2]; double ans[maxn]; void init() { memset(ai,0,sizeof(ai)); memset(bi,0,sizeof(bi)); ai[0][0]=1; for(int i=1; i<=2*1000; i++) { //w for(int j=1; j<=i; j++) { int w=j; int b=i-j; if(w<=1000&&b<1000) { ai[w][b]+=(ai[w-1][b]/2.0); if(w>b) bi[w][w+b]+=(ai[w-1][b]/2.0); } } //b for(int j=1; j<=i; j++) { int w=i-j; int b=j; if(b<=1000&&w<1000) { ai[w][b]+=(ai[w][b-1]/2.0); if(b>w) bi[b][w+b]+=(ai[w][b-1]/2.0); } } } for(int i=1; i<=1000; i++) { double tm=0; for(int j=0; j<=i*2; j++) { tm+=bi[i][j]*j; } ans[i]=tm; } } void play() { scanf("%d",&n); printf("%.2f\n",ans[n]); } int T; int main() { init(); scanf("%d",&T); while(T--) { play(); } // cout << "Hello world!" << endl; return 0; } /* Author:Chieh Because Of Coding */ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #include <stack> #include <set> #define LL long long #define INF 1e9 #define INF 1e-9 using namespace std; const int maxn=1234; int n; double ai[maxn][maxn]; double ans[maxn]; void init() { memset(ai,0,sizeof(ai)); for(int i=0; i<=1000; i++) { for(int j=0; j<=1000; j++) { int w=i; int b=j; if(w==0&&b==0)ai[i][j]=1; else { if(w!=0) { ai[w][b]+=(ai[w-1][b]/2.0); } if(b!=0) { ai[w][b]+=(ai[w][b-1]/2.0); } if(w>b) { ans[w]+=(ai[w-1][b]/2.0)*(w+b); } if(b>w) { ans[b]+=(ai[w][b-1]/2.0)*(w+b); } } } } } void play() { scanf("%d",&n); printf("%.2f\n",ans[n]); } int T; int main() { init(); scanf("%d",&T); while(T--) { play(); } // cout << "Hello world!" << endl; return 0; }