HDU 1487ガウス消元
12906 ワード
この問題、状態の創立は難しくなくて、穴は比較的に多くて、1つは数字が複数である可能性があって、また負数が現れる可能性があって、また個別の元素が期待を求めることができない可能性があって、しかしその他のいくつかの元素は期待を求めることができて、私にずっとwaを譲って、最後まで、row–やっとacをキャンセルして、本当の穴.
//
// Created by Running Photon on 2016-03-16
// Copyright (c) 2015 Running Photon. All rights reserved.
//
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x,begin())
#define ll long long
#define CLR(x) memset(x, 0, sizeof x)
using namespace std;
const double inf = 10000000000;
const int MOD = 1e9 + 7;
const int maxn = 1e4 + 10;
const int maxv = 5e2 + 10;
const double eps = 1e-5;
char s[maxv][maxv];
double A[maxv][maxv];
double e[maxv];
int n;
int vis[maxv];
int Free[maxv];
void dfs(int row, int col) {
int len = strlen(s[row]);
int cnt = 0;
CLR(e);
vis[0] = 4;
for(int i = col; i < len - 1; i++) {
if(s[row][i] == '(') {
e[vis[cnt]] += 1;
vis[++cnt] = i;
}
if(s[row][i] == ')') {
cnt--;
}
if(isdigit(s[row][i]) || s[row][i] == '-') {
e[vis[cnt]] += 1;
while(isdigit(s[row][i]) || s[row][i] == '-') {
i++;
}
i--;
}
if(isalpha(s[row][i])) e[vis[cnt]] += 1;
}
}
void debug(int edu, int var) {
for(int i = 0; i < edu; i++) {
for(int j = 0; j <= var; j++) {
printf("%f ", A[i][j]);
}
puts("");
}
puts("");
}
double res[maxv];
void Guass(int edu, int var) {
int col, row;
CLR(Free);
for(col = 0, row = 0; row < edu && col < var; col++, row++) {
int max_row = row;
for(int i = row + 1; i < edu; i++) {
if(abs(A[i][col]) > abs(A[max_row][col])) {
max_row = i;
}
}
if(max_row != row) {
for(int j = 0; j <= var; j++) {
swap(A[max_row][j], A[row][j]);
}
}
if(abs(A[row][col]) < eps) {
// row--;
Free[col] = 1;
continue;
}
for(int i = row + 1; i < edu; i++) {
if(abs(A[i][col]) < eps) continue;
double k = A[i][col] / A[row][col];
A[i][col] = 0;
for(int j = col + 1; j <= var; j++) {
A[i][j] -= A[row][j] * k;
}
}
}
debug(edu, var);
for(int i = var - 1; i >= 0; i--) {
if(abs(A[i][i]) < eps) {Free[i] = 1; continue;}
res[i] = A[i][var];
for(int j = var - 1; j > i; j--) {
if(Free[j] && abs(A[i][j]) > eps) {Free[i] = 1; break;}
res[i] -= res[j] * A[i][j];
}
res[i] /= A[i][i];
}
}
int main() {
#ifdef LOCAL
freopen("in.txt", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
// ios_base::sync_with_stdio(0);
int cas = 0;
while(scanf("%d
", &n) != EOF && n) {
printf("Game %d
", ++cas);
for(int i = 0; i < n; i++) {
gets(s[i]);
// for(int k = 0; k < 4; k++)
// s[i].erase(s[i].begin());
// cout << s[i] << endl;
}
CLR(A); CLR(e); CLR(res);
for(int i = 0; i < n; i++) A[i][i] = 1;
for(int i = 0; i < n; i++) {
vis[0] = 0;
dfs(i, 5);
stack <double> sta;
sta.push(1 / e[4]);
double tmp = 1 / e[4];
int len = strlen(s[i]);
for(int j = 5; j < len; j++) {
double x = 0;
int f = 1;
if(s[i][j] == '-') {
f = -1;
j++;
}
if(isdigit(s[i][j])) {
while(isdigit(s[i][j])) {
x = x * 10 + s[i][j] - '0';
j++;
}
j--;
A[i][n] += tmp * x * f;
}
if(isalpha(s[i][j])) {
int y = s[i][j] - 'a';
A[i][y] -= tmp;
}
if(s[i][j] == '(') {
tmp *= 1 / e[j];
sta.push(1 / e[j]);
}
if(s[i][j] == ')') {
tmp /= sta.top();
sta.pop();
}
}
}
Guass(n, n);
for(int i = 0; i < n; i++) {
if(!Free[i]) printf("Expected score for %c = %.3f
", i + 'a', res[i]);
else printf("Expected score for %c undefined
", i + 'a');
}
puts("");
}
return 0;
}