QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249080#6395. Equation Discoveringreal_sigma_teamTL 271ms3836kbC++233.6kb2023-11-12 00:30:092023-11-12 00:30:09

Judging History

This is the latest submission verdict.

  • [2023-11-12 00:30:09]
  • Judged
  • Verdict: TL
  • Time: 271ms
  • Memory: 3836kb
  • [2023-11-12 00:30:09]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

using ld = long double;

set<int> ones, two;
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(int u) {
    if (g[u].size() == 0) return "x";
    if (g[u].size() == 1) {
        if (type[u] == 0) return "sin(" + gen(g[u][0]) + ")";
        if (type[u] == 1) return "cos(" + gen(g[u][0]) + ")";
    }
    if (g[u].size() == 2) {
        switch (type[u]) {
            case 0: return "(" + gen(g[u][0]) + ")+(" + gen(g[u][1]) + ")";
            case 1: return "(" + gen(g[u][0]) + ")-(" + gen(g[u][1]) + ")";
            case 2: return "(" + gen(g[u][1]) + ")-(" + gen(g[u][0]) + ")";
            case 3: return "(" + gen(g[u][0]) + ")*(" + gen(g[u][1]) + ")";
            case 4: return "(" + gen(g[u][0]) + ")/(" + gen(g[u][1]) + ")";
            case 5: return "(" + gen(g[u][1]) + ")/(" + gen(g[u][0]) + ")";
        }
    }
}

void gen2(int i) {
    if (i == g.size()) {
//        cout << gen(0) << endl;
        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;
            }
        }
//        cout << 111 << endl;
        if (ok) {
            cout << gen(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] < 6; ++type[i]) gen2(i + 1);
    }
}

void gen() {
//    cout << "----" << endl;
//    for (auto u : g) {
//        for (auto v : u) cout << v << ' ';
//        cout << endl;
//    }
    gen2(0);
//    cout << "----" << endl;
    if (g.size() == 10) return;
    int u = -1;
    int v = g.size();
    g.push_back({});
    type.push_back(0);
    two.insert(v);
    while (1) {
        auto o = ones.upper_bound(u);
        if (o == ones.end()) break;
        u = *o;
        ones.erase(u);
        g[u].push_back(v);
        gen();
        g[u].pop_back();
        ones.insert(u);
    }
    u = -1;
    while (1) {
        auto o = two.upper_bound(u);
        if (o == two.end()) break;
        u = *o;
        if (u == v) continue;
        two.erase(u);
        ones.insert(u);
        g[u].push_back(v);
        gen();
        g[u].pop_back();
        two.insert(u);
        ones.erase(u);
    }
    g.pop_back();
    two.erase(v);
    type.pop_back();
}

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;
    g.push_back({});
    type.push_back(0);
    two.insert(0);
    gen();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3836kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

(x)*(x)

result:

ok great!!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

(sin(x))/((x)*(x))

result:

ok great!!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3736kb

input:

5
77.685777 233.057331
-66.445083 -199.335249
79.966717 239.900151
84.982130 254.946390
-31.528900 -94.586700

output:

((x)+(x))+(x)

result:

ok great!!

Test #4:

score: 0
Accepted
time: 3ms
memory: 3740kb

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:

((sin(x))/(cos(x)))+((x)-(x))

result:

ok great!!

Test #5:

score: 0
Accepted
time: 79ms
memory: 3736kb

input:

5
78.611917 -0.992212
-29.857271 1.011993
-75.513655 1.006611
68.512394 1.145128
7.961096 0.881661

output:

((sin(x))*(sin(x)))+(cos(x))

result:

ok great!!

Test #6:

score: 0
Accepted
time: 271ms
memory: 3684kb

input:

5
-78.733375 0.503570
-20.187183 0.735779
-38.984992 0.730890
47.859232 0.622831
-19.657164 0.641512

output:

((x)-(x))+(sin(sin(cos(cos(x)))))

result:

ok great!!

Test #7:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

5
3.241091 -32.628130
-83.514144 86.463432
33.586619 40.691607
41.123543 -147.352644
26.896326 27.404018

output:

(x)/(sin(x))

result:

ok great!!

Test #8:

score: -100
Time Limit Exceeded

input:

20
-4.908422 -0.693287
3.569189 0.328182
1.946572 -0.667466
6.515336 -0.829948
-1.394076 0.752980
6.722989 0.831881
1.241795 0.835231
-2.443177 -0.143098
-4.180762 -0.803482
1.511247 0.589509
0.627755 0.554244
-1.865604 -0.470029
-4.756347 -0.656984
1.850611 -0.426016
6.580133 -0.474416
6.861815 -0....

output:


result: