QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104267 | #6395. Equation Discovering | Melacau# | RE | 2ms | 3952kb | C++17 | 2.8kb | 2023-05-09 21:19:19 | 2023-05-09 21:19:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std; namespace {
using T = long double;
const char endl = '\n';
const int maxN = 1e6 + 5;
const string uops = "sc";
const string bops = "+-*/";
using Arr = array<T, 21>;
int n;
Arr x, y;
struct S { char op; int ld, li, rd, ri; Arr x; };
vector<S> f[10];
Arr uop(char op, const Arr& a) {
Arr ret;
if(op == 's') for(int i = 1; i <= n; i++) ret[i] = sin(a[i]);
if(op == 'c') for(int i = 1; i <= n; i++) ret[i] = cos(a[i]);
return ret;
}
pair<Arr, bool> bop(char op, const Arr& a, const Arr& b) {
Arr ret;
if(op == '+') for(int i = 1; i <= n; i++) ret[i] = a[i] + b[i];
if(op == '-') for(int i = 1; i <= n; i++) ret[i] = a[i] - b[i];
if(op == '*') for(int i = 1; i <= n; i++) ret[i] = a[i] * b[i];
if(op == '/') {
for(int i = 1; i <= n; i++) if(b[i] < 0.01) return { Arr{}, false };
for(int i = 1; i <= n; i++) ret[i] = a[i] / b[i];
}
return { ret, true };
}
T diff(const Arr& a) {
T ret = 0;
for(int i = 1; i <= n; i++)
ret = max(ret, abs(a[i] - y[i]) / max<T>(1, abs(y[i])));
return ret;
}
void print(const S& s, bool fst = true) {
if(s.op == 'x') return cout << 'x', void();
if(s.op == 's') return cout << "sin(", print(f[s.ld][s.li], false), cout << ')', void();
if(s.op == 'c') return cout << "cos(", print(f[s.ld][s.li], false), cout << ')', void();
if(!fst) cout << '(';
print(f[s.ld][s.li], false);
cout << s.op;
print(f[s.rd][s.ri], false);
if(!fst) cout << ')';
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
f[0].push_back(S{ 'x', -1, -1, -1, -1, x });
for(int d = 1; d <= 9; d++) {
for(int i = 0; i < f[d - 1].size(); i++)
for(char op : uops)
f[d].push_back(S{ op, d - 1, i, -1, -1, uop(op, f[d - 1][i].x) });
for(int ld = 0, rd = d - 2; ld <= d - 2; rd = d - ++ld - 2)
for(int li = 0; li < f[ld].size(); li++)
for(int ri = 0; ri < f[rd].size(); ri++)
for(char op : bops) {
auto [x, ok] = bop(op, f[ld][li].x, f[rd][ri].x);
if(!ok) continue;
f[d].push_back(S{ op, ld, li, rd, ri, x });
}
for(auto& s : f[d]) if(diff(s.x) < 1e-3) {
print(s);
return;
}
}
cout << "??";
abort();
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1; // cin >> t;
for(int i = 1; i <= t; i++) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3548kb
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: 3952kb
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: 2ms
memory: 3596kb
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
Dangerous Syscalls
input:
5 25.032427 -0.100652 38.727324 1.658518 27.684334 -0.669555 64.282391 8.275303 52.640700 -0.962660