今日解いた問題たち④
今日は軽めです。
107B - Basketball Team
確率の計算を普通にやる。
#include<stdio.h> #include<algorithm> using namespace std; int d[1000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<b;i++)scanf("%d",d+i); c--; d[c]--; int e=1; for(int i=0;i<b;i++)e+=d[i]; if(e<a){ printf("-1.0\n"); return 0; } double q=(double)a/e; double p=1; for(int i=0;i<a-1;i++){ p*=e-i-1-d[c]; p/=e-i-1; } printf("%.9f\n",1.0-p); }
273B - Dima and Two Sequences
階乗の積/2の累乗数みたいになるので、2の累乗数のほうの指数をもっておく。
#include<stdio.h> #include<algorithm> using namespace std; int b[100000]; int c[100000]; int e[200000]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); for(int i=0;i<a;i++)scanf("%d",c+i); int d; scanf("%d",&d); long long ret=1; int div=0; for(int i=0;i<a;i++){ if(b[i]==c[i])div++; e[i*2]=b[i]; e[i*2+1]=c[i]; } std::sort(e,e+a*2); e[a*2]=1999999999; int last=e[0]; int ren=1; for(int i=1;i<a*2+1;i++){ if(last!=e[i]){ for(int j=1;j<=ren;j++){ int t=j; while(div>0&&t%2==0){ t/=2; div--; } ret=ret*t%d; } ren=1; last=e[i]; }else ren++; } printf("%I64d\n",ret); }