結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー akakimidori
提出日時 2017-06-05 16:47:24
言語 C90
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 1,765 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 24,408 KB
実行使用メモリ 8,348 KB
最終ジャッジ日時 2024-09-22 06:49:21
合計ジャッジ時間 4,748 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 TLE * 1 -- * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘run’:
main.c:70:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |   scanf("%d%lf%lf",&len,&pa,&pb);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:75:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   75 |     scanf("%d",a+i);
      |     ^~~~~~~~~~~~~~~
main.c:78:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   78 |     scanf("%d",b+i);
      |     ^~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>

void sort173(int *a,int n){
  int i,j;
  for(i=1;i<n;i++){
    int p=a[i];
    j=i-1;
    while(j>=0 && a[j]>p){
      a[j+1]=a[j];
      j--;
    }
    a[j+1]=p;
  }
  return;
}

int len;
double pa,pb;

double calc(int s,int *a,int *b,int n,int fa,int fb,double p){
  if(n==0) return (s>0?1:0)*p;
  if(n==1){
    int i,j;
    i=j=0;
    while(!((fa>>i)&0x01)) i++;
    while(!((fb>>j)&0x01)) j++;
    int sign=(a[i]-b[j]>0?1:-1);
    double res=calc(s+sign*(a[i]+b[j]),a,b,n-1,fa^(1<<i),fb^(1<<j),p);
    return res;
  }

  if(p<1e-9) return p*0.5;

  int i,j;
  i=j=0;
  while(!((fa>>i)&0x01)) i++;
  while(!((fb>>j)&0x01)) j++;

  int sign=(a[i]-b[j]>0?1:-1);
  double res=calc(s+sign*(a[i]+b[j]),a,b,n-1,fa^(1<<i),fb^(1<<j),p*pa*pb);

  int k,l;
  for(k=i+1;k<len;k++){
    if((fa>>k)&0x01){
      int sign=(a[k]-b[j]>0?1:-1);
      res+=calc(s+sign*(a[k]+b[j]),a,b,n-1,fa^(1<<k),fb^(1<<j),p*(1-pa)/(n-1)*pb);
    }
  }
  for(l=j+1;l<len;l++){
    if((fb>>l)&0x01){
      int sign=(a[i]-b[l]>0?1:-1);
      res+=calc(s+sign*(a[i]+b[l]),a,b,n-1,fa^(1<<i),fb^(1<<l),p*pa*(1-pb)/(n-1));
    }
  }
  for(k=i+1;k<len;k++){
    if((fa>>k)&0x01){
      for(l=j+1;l<len;l++){
        if((fb>>l)&0x01){
          int sign=(a[k]-b[l]>0?1:-1);
          res+=calc(s+sign*(a[k]+b[l]),a,b,n-1,fa^(1<<k),fb^(1<<l),p*(1-pa)*(1-pb)/(n-1)/(n-1));
        }
      }
    }
  }
  return res;
}

void run(void){
  scanf("%d%lf%lf",&len,&pa,&pb);
  int a[20];
  int b[20];
  int i;
  for(i=0;i<len;i++){
    scanf("%d",a+i);
  }
  for(i=0;i<len;i++){
    scanf("%d",b+i);
  }
  sort173(a,len);
  sort173(b,len);

  double ans=calc(0,a,b,len,(1<<len)-1,(1<<len)-1,1);
  printf("%.4lf\n",ans);

  return;
}

int main(void){
  run();
  return 0;
}
0