Chocolate Problem
description:
Sandy played a game on a big package of chocolates in several colors. Each time he took one chocolate from the package and placed it on the table. If there were two chocolates of the same color on the table, he ate both of them. The problem asks students to determine if there are C colors of chocolates in the package (colors are distributed evenly), after N chocolates are taken from the package, what the probability that there are exactly M chocolates on the table is.
source:
right:chenyuxi
--------------------------------------------------------------------------------------------------
#include<iostream>using namespace std;int c,n,m,i,j;double p[101],b[101];int main(){ while(scanf("%d",&c)) { if (c==0) break; scanf("%d%d",&n,&m); if(m>c||(m+n)&1) { printf("0.000\n"); continue; } for(i=1;i<=c;i++) { p[i]=0;b[i]=(double)i/c; } p[0]=1; for(i=1;i<=n&&i<500;i++) for(j=i&1;j<=c;j+=2) p[j]=(j?p[j-1]*b[c-j+1]:0)+((j<c)?p[j+1]*b[j+1]:0); printf("%.3f\n",p[m]); } return 0;}
--------------------------------------------------------------------------------------------------
wrong 1: z__jj
--------------------------------------------------------------------------------------------------
#include<iostream>using namespace std;double **d;int main(){ int c,n,m;d=new double*[2]; while(scanf("%d",&c)&&c) { scanf("%d%d",&n,&m); if(((n-m)&1)||m>c||m>n){printf("0.000\n");continue;} if(n>300)n=300+n%2; d[0]=new double[c+1];d[1]=new double[c+1]; d[0][0]=1.0; for(int i=1;i<=c;i++)d[0][i]=0.0; int a,b;double C=1.0/c; for(int i=1;i<=n;i++) { int I=i&1,I1=(i-1)&1; d[I][c]=d[I1][c-1]*C; d[I][0]=d[I1][1]*C; if(I){a=2;b=1;} else {a=1;b=2;} for(int j=a;j<c;j+=2)d[I][j]=0; for(int j=b;j<c;j+=2) { d[I][j]=d[I1][j+1]*(j+1.0)*C+d[I1][j-1]*(c+1.0-j)*C; } } printf("%.3lf\n",d[n&1][m]); } return 0;
}
--------------------------------------------------------------------------------------------------
wrong2: ic07112
--------------------------------------------------------------------------------------------------
#include <iostream>using namespace std;double s[2002][201];int main(){ int n,m,c,i,j; scanf("%d",&c); while (c!=0) { scanf("%d%d",&n,&m); memset(s,0,sizeof(s)); if (m>c || m>n) printf("0.000\n"); else { if (n>1000) n=1000+n%2; s[1][1]=1; s[1][0]=0; for (i=2;i<=n;i++) for (j=0;j<=c;j++) { if (j==0) s[i][j] = s[i-1][1] / c; else if (j==c) s[i][j] = s[i-1][c-1] / c; else s[i][j] = s[i-1][j-1]*(c-(j-1))/c + s[i-1][j+1]*(j+1)/c; } printf("%.3lf\n",s[n][m]); } scanf("%d",&c); } return 0;}
--------------------------------------------------------------------------------------------------
wrong3: ic07714
--------------------------------------------------------------------------------------------------
#include "stdio.h" #include "memory.h"double a[800][105];int c;double cal(int i,int j){ if(a[i][j]>=0) return a[i][j]; if(i==0) { if(j==0) return a[i][j]=1; else return a[i][j]=0; } if(j==0) a[i][0]=cal(i-1,1)*1.0/(double)c; else if(j==c) a[i][c]=cal(i-1,c-1)*1.0/(double)c; else a[i][j]=cal(i-1,j-1)*(c+1-j)/(double)c+cal(i-1,j+1)*(j+1)*1.0/(double)c; return a[i][j];}int main(){ int n,m; while(1) { // memset(a,-1,sizeof(a)); scanf("%d",&c); if(!c) return 0; scanf("%d%d",&n,&m);if(n>800) n=800+n%2; for(int i=0;i<n;i++) for(int j=0;j<105;j++) { a[i][j]=-1; if((i%2)+(j%2)==1) a[i][j]=0; } if (m>c||m>n){ printf("0.000\n"); continue; } double result=cal(n,m); printf("%.3lf\n",result); } return 0;}
--------------------------------------------------------------------------------------------------
wrong4: aquarius2
--------------------------------------------------------------------------------------------------
#include<iostream>using namespace std; #define in(x) scanf("%d",&(x)) #define out3(x) printf("%.3lf\n",(x))double p[2][111];int main(){ int n,m,k,c,i,j; while(in(c) && c) { in(n);in(m); if(m>c || m>n || m<0 || n<0 || (n-m)%2) { out3(0); continue; } memset(p,0,sizeof(p)); p[0][0]=1.0; k=0; int up=n; if(n>400 && n%2==1) up=401; else if(n>400 && n%2==0) up=400; for(i=0; i<up;i++){ k=1-k; p[k][0]=p[1-k][1]/c; for(j=1;j<=c;j++){ p[k][j]=(p[1-k][j+1]*(j+1) + p[1-k][j-1]*(c-j+1))/double(c); } } out3(p[k][m]); }}
--------------------------------------------------------------------------------------------------
wrong5: facer
--------------------------------------------------------------------------------------------------
#include <iostream> #include <iomanip>using namespace std;const int maxn=1005;const int w=4000;double c[maxn],d[maxn],fen[maxn];int r,n,m;double make(){ int i,j; if ((n-m)%2) return 0; if (m>n) return 0; if (m>r) return 0; for (i=0;i<=r;i++) fen[i]=double(i)/r; for (i=0;i<=r;i++) c[i]=0;c[0]=1; for (i=1;i<=n;i++) { if (i>w&&(n-i)%2==0) break; for (j=0;j<=r+1;j++) d[j]=0; for (j=0;j<=r;j++) { if (j>0) d[j-1]+=c[j]*fen[j]; d[j+1]+=c[j]*fen[r-j]; } for (j=0;j<=r;j++) c[j]=d[j]; } return c[m];}int main(){ double g; while (true) { cin >> r; if (r==0) break; cin >> n >> m; g=make(); cout << setiosflags(ios::fixed) << setprecision(3) << g << endl; }}
--------------------------------------------------------------------------------------------------