結果

問題 No.66 輝け☆全国たこやき杯
ユーザー 古寺いろは古寺いろは
提出日時 2015-04-13 08:23:05
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 750 bytes
コンパイル時間 1,129 ms
コンパイル使用メモリ 145,732 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-17 19:56:30
合計ジャッジ時間 1,754 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

int S[1 << 10];

vector<double> dfs(int start, int num){
	vector<double> ret(num);
	if (num == 1){
		ret[0] = 1;
		return ret;
	}
	vector <double> a = dfs(start, num / 2);
	vector <double> b = dfs(start + num / 2, num / 2);
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			double p = a[i] * b[j];
			int ap = start + i;
			int bp = start + num / 2 + j;
			ret[i] += p * S[ap] * S[ap] / (S[ap] * S[ap] + S[bp] * S[bp]);
			ret[num/2 + j] += p * S[bp] * S[bp] / (S[ap] * S[ap] + S[bp] * S[bp]);
		}
	}
	return ret;
}

int main(){
	int M;
	cin >> M;
	for (int i = 0; i < (1<<M); i++)
	{
		cin >> S[i];
	}
	vector<double> ans = dfs(0, 1 << M);
	printf("%.14f\n", ans[0]);
}
0