QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#249154#6395. Equation Discoveringreal_sigma_teamWA 1ms3668kbC++233.5kb2023-11-12 01:34:492023-11-12 01:34:49

Judging History

你现在查看的是最新测评结果

  • [2023-11-12 01:34:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3668kb
  • [2023-11-12 01:34:49]
  • 提交

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