QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#177258 | #6395. Equation Discovering | mendicillin2 | WA | 132ms | 151332kb | C++17 | 3.6kb | 2023-09-12 19:23:44 | 2023-09-12 19:23:44 |
Judging History
answer
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;
template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
template <class F>
struct ycr {
F f;
template <class T>
explicit ycr(T&& f_) : f(forward<T>(f_)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return f(ref(*this), forward<Args>(args)...);
}
};
template <class F>
decltype(auto) yc(F&& f) {
return ycr<decay_t<F>>(forward<F>(f));
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
int N; cin >> N;
using D = double;
vector<D> xs(N), ys(N);
for (int i = 0; i < N; i++) {
cin >> xs[i] >> ys[i];
}
auto check = [&](string expr, vector<D> cur) -> void {
for (int i = 0; i < N; i++) {
if (abs(cur[i] - ys[i]) / max<D>(1, abs(ys[i])) > 1e-3) return;
}
cout << expr << '\n';
exit(0);
};
const int L = 10;
vector<vector<pair<string, vector<D>>>> vals(L);
vals[0].push_back({"x", xs});
vector<D> t(N);
for (int c = 1; c < L; c++) {
// sin/cos
for (const auto& [expr, s] : vals[c-1]) {
{
for (int i = 0; i < N; i++) {
t[i] = sin(s[i]);
}
auto new_expr = "sin(" + expr + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
{
for (int i = 0; i < N; i++) {
t[i] = cos(s[i]);
}
auto new_expr = "cos(" + expr + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
for (int c0 = 0; c0+1 <= c-1-c0; c0++) {
int c1 = c-1-c0;
for (const auto& [expr0, s0] : vals[c0]) {
for (const auto& [expr1, s1] : vals[c1]) {
for (int i = 0; i < N; i++) {
t[i] = s0[i] + s1[i];
}
auto new_expr = "(" + expr0 + ")+(" + expr1 + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
for (const auto& [expr0, s0] : vals[c0]) {
for (const auto& [expr1, s1] : vals[c1]) {
for (int i = 0; i < N; i++) {
t[i] = s0[i] - s1[i];
}
auto new_expr = "(" + expr0 + ")-(" + expr1 + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
for (const auto& [expr0, s0] : vals[c0]) {
for (const auto& [expr1, s1] : vals[c1]) {
for (int i = 0; i < N; i++) {
t[i] = s1[i] - s0[i];
}
auto new_expr = "(" + expr1 + ")-(" + expr0 + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
for (const auto& [expr0, s0] : vals[c0]) {
for (const auto& [expr1, s1] : vals[c1]) {
for (int i = 0; i < N; i++) {
t[i] = s0[i] * s1[i];
}
auto new_expr = "(" + expr0 + ")*(" + expr1 + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
for (const auto& [expr0, s0] : vals[c0]) {
for (const auto& [expr1, s1] : vals[c1]) {
bool works = true;
for (int i = 0; i < N; i++) {
if (abs(s1[i]) < 1e-2) {
works = false;
break;
}
t[i] = s0[i] / s1[i];
}
if (!works) continue;
auto new_expr = "(" + expr0 + ")/(" + expr1 + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
for (const auto& [expr0, s0] : vals[c0]) {
for (const auto& [expr1, s1] : vals[c1]) {
bool works = true;
for (int i = 0; i < N; i++) {
if (abs(s0[i]) < 1e-2) {
works = false;
break;
}
t[i] = s1[i] / s0[i];
}
if (!works) continue;
auto new_expr = "(" + expr1 + ")/(" + expr0 + ")";
check(new_expr, t);
vals[c].push_back({new_expr, t});
}
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5268kb
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
output:
(x)*((sin(x))+((x)-(sin(x))))
result:
ok great!!
Test #2:
score: 0
Accepted
time: 1ms
memory: 4044kb
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: 4764kb
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)+((sin(x))/(x))))
result:
ok great!!
Test #4:
score: 0
Accepted
time: 2ms
memory: 5320kb
input:
5 25.032427 -0.100652 38.727324 1.658518 27.684334 -0.669555 64.282391 8.275303 52.640700 -0.962660
output:
(x)*((sin(x))/((x)*(cos(x))))
result:
ok great!!
Test #5:
score: -100
Wrong Answer
time: 132ms
memory: 151332kb
input:
5 78.611917 -0.992212 -29.857271 1.011993 -75.513655 1.006611 68.512394 1.145128 7.961096 0.881661
output:
((x)+((cos(x))*((x)-((x)*(cos(x))))))/(x)
result:
wrong answer complexity too big, 12