Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
yukicoder No.66
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define NUM 1100
typedef long long ll;
using namespace std;
int inputValue(){
int a;
cin >> a;
return a;
};
void inputArray(int * p, int a){
rep(i, a){
cin >> p[i];
}
};
void inputVector(vector<int> * p, int a){
rep(i, a){
int input;
cin >> input;
p -> push_back(input);
}
}
template <typename T>
void output(T a, int precision) {
if(precision > 0){
cout << setprecision(precision) << a << "\n";
}
else{
cout << a << "\n";
}
}
int power(int n, int m){
int ret = 1;
rep(i, m){
ret *= n;
}
return ret;
}
// a = 01011, b = 01000 d = 5 -> ret = d - 3 = 1
int digit(int a, int b, int d){
int num = 0;
int c = 1 << (d - 1);
rep(i, d){
if ((c & a) == (c & b)) {
c = c >> 1;
num++;
}
else{
break;
}
}
return d - num;
}
double P[NUM] = {0};
double dp[NUM][11] = {1};
int main(int argc, const char * argv[]) {
// source code
int M = inputValue();
int N = power(2,M);
rep(i, N){
cin >> P[i];
}
rep(i, N){
dp[i][0] = 1;
}
repd(i, 1, M + 1){
rep(j, N){
double temp = 0.0;
rep(k, N){
if (digit(j, k, M) == i && j != k) {
temp += dp[k][i - 1] * P[j] * P[j] / (P[j] * P[j] + P[k] * P[k]);
}
}
dp[j][i] = dp[j][i - 1] * temp;
}
}
output(dp[0][M], 10);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.