记录编号	46637	评测结果	AAAAAAAAAA
题目名称	[NOIP 2005]等价表达式	最终得分	100
用户昵称	codewaysky	是否通过	通过
代码语言	C++	运行时间	0.395 s
提交时间	2012-10-29 07:50:43	内存使用	3.16 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <stack>
#include <ctime>

using namespace std;

#define UNSURE '$'
#define DIV '#'

const int kMaxN = 30;

int n;
string stdstr;
string optional[kMaxN];
int cnt[kMaxN];

long double CalcPostfix(const string &str, long double value) {
    stack<long double> s;

    if (str.size() == 0) return 0.0;
    
    for (int i = 0; i < (int)str.size(); ) {
	char c = str[i];

	if (c == DIV) {
	    i++;
	    continue;
	} else if ((c >= '0' && c <= '9') || c == '.') {
	    int pos = str.find_first_of("#$+-*^", i);
	    if (pos == (int)string::npos) {
		s.push(atof(str.substr(i).c_str()));
		break;
	    } else {
		s.push(atof(str.substr(i, pos - i + 1).c_str()));
		i = pos;
	    }
	} else if (c == UNSURE) {
	    s.push(value);
	    i++;
	} else if (c == '+') {
	    long double t1 = s.top();
	    s.pop();
	    long double t2 = s.top();
	    s.pop();
	    s.push(t1 + t2);
	    i++;
	} else if (c == '-') {
	    long double t2 = s.top();
	    s.pop();
	    long double t1 = s.top();
	    s.pop();
	    s.push(t1 - t2);
	    i++;
	} else if (c == '*') {
	    long double t1 = s.top();
	    s.pop();
	    long double t2 = s.top();
	    s.pop();
	    s.push(t1 * t2);
	    i++;
	} else if (c == '^') {
	    long double t2 = s.top();
	    s.pop();
	    long double t1 = s.top();
	    s.pop();
	    s.push(pow(t1, t2));
	    i++;
	} else {
	    i++;
	}
    }

    return s.top();
}

long double Calc(const string &str, long double value) {
    string postfix;
    stack<char> s;
    bool isnum = false;

    for (int i = 0; i < (int)str.size(); i++) {
	char c = str[i];

	if (c == 'a') {
	    isnum = true;
	    postfix.push_back(UNSURE);
	} else if ((c >= '0' && c <= '9') || c == '.') {
	    isnum = true;
	    postfix.push_back(c);
	} else if (c == '(') {
	    if (isnum) {
		isnum = false;
		postfix.push_back(DIV);
	    }
	    s.push(c);
	} else if (c == ')') {
	    if (isnum) {
		isnum = false;
		postfix.push_back(DIV);
	    }

	    while (!s.empty() && s.top() != '(') {
		postfix.push_back(s.top());
		s.pop();
	    }
	    if (!s.empty()) {
		s.pop();
	    }
	} else if (c == '+' || c == '-') {
	    if (isnum) {
		isnum = false;
		postfix.push_back(DIV);
	    }

	    while (!s.empty() && s.top() != '(') {
		postfix.push_back(s.top());
		s.pop();
	    }
	    s.push(c);
	} else if (c == '*') {
	    if (isnum) {
		isnum = false;
		postfix.push_back(DIV);
	    }

	    while (!s.empty() && s.top() != '(' && s.top() != '+' && s.top() != '-') {
		postfix.push_back(s.top());
		s.pop();
	    }
	    s.push(c);
	} else if (c == '^') {
	    if (isnum) {
		isnum = false;
		postfix.push_back(DIV);
	    }

	    while (!s.empty() && s.top() != '(' && s.top() != '+' && s.top() != '-' && s.top() != '*') {
		postfix.push_back(s.top());
		s.pop();
	    }
	    s.push(c);
	} else {
	    continue;
	}
    }
    while (!s.empty()) {
	postfix.push_back(s.top());
	s.pop();
    }

    return CalcPostfix(postfix, value);
}

void Work() {
    srand48(time(NULL));
    for (int setp = 1; setp <= 200; setp++) {
	long double num = drand48();
	long double ans = Calc(stdstr, num);
	for (int i = 1; i <= n; i++) {
	    long double tmp = Calc(optional[i], num);
	    if (fabsl(ans-tmp) < fabsl(ans) * 1e-6) {
		cnt[i]++;
	    }
	}
    }

    int maxcnt = 0;
    for (int i = 1; i <= n; i++) {
	maxcnt = max(maxcnt, cnt[i]);
    }

    for (int i = 1; i <= n; i++) {
	if (cnt[i] >= 180) {
	    printf("%c", 'A' + i - 1);
	}
    }
    printf("\n");
}

int main() {
    freopen("equal.in", "r", stdin);
    freopen("equal.out", "w", stdout);
    ios::sync_with_stdio(false);

    getline(cin, stdstr);
    cin >> n;
    getline(cin, optional[0]);
    for (int i = 1; i <= n; i++) {
	getline(cin, optional[i]);
    }

    Work();

    fclose(stdin);
    fclose(stdout);
    return 0;
}