QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249080 | #6395. Equation Discovering | real_sigma_team | TL | 271ms | 3836kb | C++23 | 3.6kb | 2023-11-12 00:30:09 | 2023-11-12 00:30:09 |
Judging History
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....