結果

問題 No.66 輝け☆全国たこやき杯
ユーザー goodbatongoodbaton
提出日時 2015-08-06 21:11:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,366 bytes
コンパイル時間 950 ms
コンパイル使用メモリ 71,696 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-25 04:16:11
合計ジャッジ時間 1,804 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 4 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>

typedef long long ll;
using namespace std;

#define mod 1000000009
#define INF 1000000000
#define LLINF 2000000000000000000LL
#define PI 3.1415926536

#define SIZE 1024

int m,s[SIZE],n=1;

double pro[SIZE];

void dfs(int l,int r){
    
    double pro2[SIZE];
    
    if(l==r){
        pro[l]=1;
        return;
    }
    
    dfs(l,(l+r)/2);
    dfs((l+r)/2+1,r);

    for(int i=l;i<=(l+r)/2;i++){
        double p = 0;
        
        for(int j=(l+r)/2+1;j<=r;j++){
            
            p+=(s[i]*s[i])/(double)(s[i]*s[i]+s[j]*s[j])*pro[j];
            
        }
        
        pro2[i]=p*pro[i];
    }
    
    for(int i=(l+r)/2+1;i<=r;i++){
        double p = 0;
        
        for(int j=l;j<=(l+r)/2;j++){
            
            p+=(s[i]*s[i])/(double)(s[i]*s[i]+s[j]*s[j])*pro[j];
            
        }
        
        pro2[i]=p*pro[i];
    }
    
    for(int i=l;i<=r;i++)
        pro[i] = pro2[i];
    
    return;
}

int main(){
    
    scanf("%d",&m);
    
    for(int i=0;i<m;i++) n*=2;
    
    for(int i=0;i<n;i++){
        scanf("%d",&s[i]);
    }
    
    dfs(0,n-1);
    
    printf("%.15lf",pro[0]);
    
    return 0;
}
0