QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104920 | #6395. Equation Discovering | ckiseki# | WA | 66ms | 3628kb | C++20 | 4.0kb | 2023-05-12 15:12:40 | 2023-05-12 15:12:43 |
Judging History
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