QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104920#6395. Equation Discoveringckiseki#WA 66ms3628kbC++204.0kb2023-05-12 15:12:402023-05-12 15:12:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 15:12:43]
  • 评测
  • 测评结果:WA
  • 用时:66ms
  • 内存:3628kb
  • [2023-05-12 15:12:40]
  • 提交

answer

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

#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

namespace {

using llf = long double;

constexpr int maxn = 20;

pair<llf, llf> f[maxn];

llf readf() {
    int x, y;
    scanf("%d.%d", &x, &y);
    if (x < 0)
        return x - y / 1e6l;
    return x + y / 1e6l;
}

const string op_name[] = {
    "+",
    "-",
    "*",
    "/",
    "sin",
    "cos"
};

struct node {
    node *lc, *rc;
    int op;
    node() : lc(nullptr), rc(nullptr), op(-1) {}
};

llf err(llf a, llf b) {
    return abs(a - b) / max<llf>(1, abs(b));
}

optional<llf> eval(node *r, llf x) {
    if (r == nullptr)
        return x;
    if (r->op < 4) {
        auto lhs = eval(r->lc, x);
        auto rhs = eval(r->rc, x);
        if (not lhs or not rhs)
            return nullopt;
        if (r->op == 0)
            return *lhs + *rhs;
        if (r->op == 1)
            return *lhs - *rhs;
        if (r->op == 2)
            return *lhs * *rhs;
        if (r->op == 3) {
            if (abs(*rhs) < 0.01)
                return nullopt;
            return *lhs / *rhs;
        }
        __builtin_unreachable();
    } else {
        auto v = eval(r->lc, x);
        if (not v)
            return nullopt;
        if (r->op == 4)
            return sin(*v);
        if (r->op == 5)
            return cos(*v);
        __builtin_unreachable();
    }
}

void dump(node *r) {
    putchar('(');
    if (r == nullptr) {
        putchar('x');
    } else if (r->op < 2) {
        dump(r->lc);
        printf(op_name[r->op].c_str());
        dump(r->rc);
    } else if (r->op < 4) {
        dump(r->lc);
        printf(op_name[r->op].c_str());
        dump(r->rc);
    } else {
        printf(op_name[r->op].c_str());
        putchar('(');
        dump(r->lc);
        putchar(')');
    }
    putchar(')');
}

void check(node *r, int n) {
    for (int i = 0; i < n; ++i) {
        if (auto v = eval(r, f[i].first); not v or err(*v, f[i].second) > 1e-3) {
            return;
        }
    }
    dump(r);
    putchar('\n');
    exit(0);
}

void solve(vector<node *> &v, size_t p, int b, int n) {
    if (p == v.size()) {
        check(v[0], n);
        return;
    }
    node *cur = v[p];
    node lhs{}, rhs{};
    if (b >= 2) {
        for (int i = 0; i < 4; ++i) {
            cur->op = i;
            
            cur->lc = nullptr, cur->rc = nullptr;
            solve(v, p + 1, b - 2, n);

            cur->lc = nullptr, cur->rc = &rhs;
            v.push_back(cur->rc);
            solve(v, p + 1, b - 2, n);
            v.pop_back();
            
            cur->lc = &lhs, cur->rc = nullptr;
            v.push_back(cur->lc);
            solve(v, p + 1, b - 2, n);
            v.pop_back();

            cur->lc = &lhs, cur->rc = &rhs;
            v.push_back(cur->lc), v.push_back(cur->rc);
            solve(v, p + 1, b - 2, n);
            v.pop_back(), v.pop_back();
        }
    }
    if (b >= 1) {
        for (int i = 4; i < 6; ++i) {
            cur->op = i;
            
            cur->lc = nullptr;
            solve(v, p + 1, b - 2, n);

            cur->lc = &lhs;
            v.push_back(cur->lc);
            solve(v, p + 1, b - 1, n);
            v.pop_back();
        }
    }
}

} // namespace

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        f[i].first = readf();
        f[i].second = readf();
    }
    node r{};
    vector<node *> v = {&r};
    solve(v, 0, 9, n);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3576kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

((x)+(((x)*(x))-(x)))

result:

ok great!!

Test #2:

score: 0
Accepted
time: 2ms
memory: 3628kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

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

result:

ok great!!

Test #3:

score: 0
Accepted
time: 2ms
memory: 3508kb

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: -100
Wrong Answer
time: 66ms
memory: 3540kb

input:

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

output:


result:

wrong output format Unexpected end of file - token expected