QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#471449 | #6395. Equation Discovering | UESTC_Snow_Halation | WA | 380ms | 173320kb | C++14 | 4.0kb | 2024-07-10 21:15:01 | 2024-07-10 21:15:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr int max_n = 500;
double eps = 1e-6;
struct layer {
char op;
int ld, rd;
int ll, rl;
vector<long double> value;
layer(char op, int ld, int ll, int rd, int rl, vector<long double> value) : op(op), ld(ld), ll(ll), rd(rd), rl(rl), value(std::move(value)) {}
string to_string();
};
vector<layer> fx[20];
vector<long double> ans;
int n;
string layer::to_string() {
string s;
switch (op) {
case 's':
s = "sin" + fx[ll][ld].to_string();
break;
case 'c':
s = "cos" + fx[ll][ld].to_string();
break;
case '+':
case '-':
case '*':
case '/':
s = fx[ll][ld].to_string() + op + fx[rl][rd].to_string();
break;
case 'x':
s = "x";
break;
}
return "(" + s + ")";
}
bool equ(vector<ld>& x) {
for (int i = 0; i < n; ++i) {
if (abs(x[i] - ans[i]) > eps) return false;
}
return true;
}
void solve() {
cin >> n;
fx[0].emplace_back('x', 0, 0, 0, 0, vector<ld>(n));
ans.resize(n);
for (int i = 0; i < n; ++i) {
cin >> fx[0][0].value[i] >> ans[i];
}
for (int i = 1; i <= 9; ++i) {
for (int j = 0; j < fx[i - 1].size(); ++j) {
fx[i].emplace_back('s', j, i - 1, 0, 0, vector<ld>(n));
for (int k = 0; k < n; ++k) {
fx[i].back().value[k] = sin(fx[i - 1][j].value[k]);
}
if (equ(fx[i].back().value)) {
cout << fx[i].back().to_string() << '\n';
return;
}
fx[i].emplace_back('c', j, i - 1, 0, 0, vector<ld>(n));
for (int k = 0; k < n; ++k) {
fx[i].back().value[k] = cos(fx[i - 1][j].value[k]);
}
if (equ(fx[i].back().value)) {
cout << fx[i].back().to_string() << '\n';
return;
}
}
for (int j = 0, jj; j <= i - 2; ++j) {
jj = i - 2 - j;
for (int l = 0; l < fx[j].size(); ++l) {
for (int r = 0; r < fx[jj].size(); ++r) {
fx[i].emplace_back('+', l, j, r, jj, vector<ld>(n));
for (int k = 0; k < n; ++k) {
fx[i].back().value[k] = fx[j][l].value[k] + fx[jj][r].value[k];
}
if (equ(fx[i].back().value)) {
cout << fx[i].back().to_string() << '\n';
return;
}
fx[i].emplace_back('-', l, j, r, jj, vector<ld>(n));
for (int k = 0; k < n; ++k) {
fx[i].back().value[k] = fx[j][l].value[k] - fx[jj][r].value[k];
}
if (equ(fx[i].back().value)) {
cout << fx[i].back().to_string() << '\n';
return;
}
fx[i].emplace_back('*', l, j, r, jj, vector<ld>(n));
for (int k = 0; k < n; ++k) {
fx[i].back().value[k] = fx[j][l].value[k] * fx[jj][r].value[k];
}
if (equ(fx[i].back().value)) {
cout << fx[i].back().to_string() << '\n';
return;
}
fx[i].emplace_back('/', l, j, r, jj, vector<ld>(n));
for (int k = 0; k < n; ++k) {
if (abs(fx[jj][r].value[k]) < 0.15) {
fx[i].pop_back();
break;
}
fx[i].back().value[k] = fx[j][l].value[k] / fx[jj][r].value[k];
}
if (equ(fx[i].back().value)) {
cout << fx[i].back().to_string() << '\n';
return;
}
}
}
}
}
// for (int i =0; i <= 9; ++i) {
// for (auto& item: fx[i]) {
// cout << item.to_string();
// for (auto& v: item.value) {
// cout << ", " << v;
// }
// cout << '\n';
// }
// }
}
int main() {
// freopen("code.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
// scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
// cout << "Case " << i << ": ";
solve();
}
return 0;
}
/*
3 3
2.4.2
.....
4.8.4
.....
2.5.3
5 5
3.4.4.4.2
.........
4.7.7.7.4
.........
4.8.7.7.4
.........
4.7.7.7.5
.........
2.4.4.4.2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4240kb
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: 1ms
memory: 4356kb
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: 4100kb
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: 19ms
memory: 12292kb
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: 0
Accepted
time: 5ms
memory: 5548kb
input:
5 78.611917 -0.992212 -29.857271 1.011993 -75.513655 1.006611 68.512394 1.145128 7.961096 0.881661
output:
((cos(x))+((sin(x))*(sin(x))))
result:
ok great!!
Test #6:
score: 0
Accepted
time: 0ms
memory: 4196kb
input:
5 -78.733375 0.503570 -20.187183 0.735779 -38.984992 0.730890 47.859232 0.622831 -19.657164 0.641512
output:
(sin(sin(cos(cos(x)))))
result:
ok great!!
Test #7:
score: 0
Accepted
time: 5ms
memory: 5236kb
input:
5 3.241091 -32.628130 -83.514144 86.463432 33.586619 40.691607 41.123543 -147.352644 26.896326 27.404018
output:
((x)*((x)/((x)*(sin(x)))))
result:
ok great!!
Test #8:
score: -100
Wrong Answer
time: 380ms
memory: 173320kb
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....
output:
result:
wrong output format Unexpected end of file - token expected