QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#249154 | #6395. Equation Discovering | real_sigma_team | WA | 1ms | 3668kb | C++23 | 3.5kb | 2023-11-12 01:34:49 | 2023-11-12 01:34:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
using ld = long double;
vector<vector<int>> g;
vector<int> type;
vector<pair<ld, ld>> eq;
ld evaluate(ld x, int u) {
if (g[u].size() == 0) return x;
if (g[u].size() == 1) {
if (type[u] == 0) return sin(evaluate(x, g[u][0]));
if (type[u] == 1) return cos(evaluate(x, g[u][0]));
}
if (g[u].size() == 2) {
switch (type[u]) {
case 0: return evaluate(x, g[u][0]) + evaluate(x, g[u][1]);
case 1: return evaluate(x, g[u][0]) - evaluate(x, g[u][1]);
case 2: return evaluate(x, g[u][1]) - evaluate(x, g[u][0]);
case 3: return evaluate(x, g[u][0]) * evaluate(x, g[u][1]);
case 4: return evaluate(x, g[u][0]) / evaluate(x, g[u][1]);
case 5: return evaluate(x, g[u][1]) / evaluate(x, g[u][0]);
}
}
}
string gen_ans(int u) {
if (g[u].size() == 0) return "x";
if (g[u].size() == 1) {
if (type[u] == 0) return "sin(" + gen_ans(g[u][0]) + ")";
if (type[u] == 1) return "cos(" + gen_ans(g[u][0]) + ")";
}
if (g[u].size() == 2) {
switch (type[u]) {
case 0: return "(" + gen_ans(g[u][0]) + ")+(" + gen_ans(g[u][1]) + ")";
case 1: return "(" + gen_ans(g[u][0]) + ")-(" + gen_ans(g[u][1]) + ")";
case 2: return "(" + gen_ans(g[u][0]) + ")*(" + gen_ans(g[u][1]) + ")";
case 3: return "(" + gen_ans(g[u][0]) + ")/(" + gen_ans(g[u][1]) + ")";
}
}
}
void gen2(int i) {
if (i == g.size()) {
bool ok = 1;
for (auto [x, y] : eq) {
auto val = evaluate(x, 0);
if (abs(val - y) / max((ld)1, abs(y)) <= 1e-3) {}
else {
ok = 0;
break;
}
}
if (ok) {
cout << gen_ans(0);
exit(0);
}
return;
}
if (g[i].size() == 0) {
type[i] = 0;
gen2(i + 1);
} else if (g[i].size() == 1) {
for (type[i] = 0; type[i] < 2; ++type[i]) gen2(i + 1);
} else {
for (type[i] = 0; type[i] < 4; ++type[i]) gen2(i + 1);
}
}
int ptr;
int gen(string s) {
if (s.empty()) return -1;
int u = ptr++;
int bal = 0;
for (int i = 0; i < s.size(); ++i) {
bal += (s[i] == '(') - (s[i] == ')');
if (bal == 0) {
int v;
v = gen(string(s.begin() + 1, s.begin() + i));
if (v != -1) g[u].push_back(v);
v = gen(string(s.begin() + i + 1, s.end()));
if (v != -1) g[u].push_back(v);
break;
}
}
return u;
}
bool ok(string s) {
int bal = 0;
bool ok = 1;
for (auto i : s) {
bal += (i == '(') - (i == ')');
ok &= bal >= 0;
}
ok &= bal == 0;
return ok;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
eq.resize(n);
for (int i = 0; i < n; ++i) cin >> eq[i].first >> eq[i].second;
for (int len = 1; len <= 10; ++len) {
for (int mask = 0; mask < (1 << (len * 2)); ++mask) {
string s(2 * len, '#');
for (int i = 0; i < 2 * len; ++i) s[i] = (mask >> i & 1) ? '(' : ')';
if (ok(s)) {
g.assign(len, {});
type.resize(len);
ptr = 0;
gen(s);
gen2(0);
}
}
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3668kb
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
output:
(x)/(x)
result:
wrong answer fail to discover