QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104806 | #6395. Equation Discovering | gapinho# | RE | 16ms | 43864kb | C++20 | 3.3kb | 2023-05-12 00:13:39 | 2023-05-12 00:13:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = __int128_t;
#define int long long
using ii = pair<int, int>;
// #define endl '\n'
const int ms = 1e6;
const int mod = 998244353;
const double eps = 1e-3;
int l[ms], r[ms];
string op[ms];
int lo[10], hi[10];
double dp[23][ms];
bool poss[23][ms];
int z = 1;
double val[23];
double expe[23];
int cmp(double a, double b) {
if(abs(a-b)/max(1.0, abs(b)) <= eps) return 0;
if(a < b) return -1;
if(a > b) return 1;
}
void calc(int id, int u) {
poss[id][u] = 1;
if(op[u] == "x") {
dp[id][u] = val[id];
return;
}
if(!poss[id][l[u]]) {
poss[id][u] = 0;
return;
}
if(op[u] == "sin") {
dp[id][u] = sin(dp[id][l[u]]);
return;
}
if(op[u] == "cos") {
dp[id][u] = cos(dp[id][l[u]]);
return;
}
if(!poss[id][r[u]]) {
poss[id][u] = 0;
return;
}
double x = dp[id][l[u]];
double y = dp[id][r[u]];
if(op[u] == "+") {
dp[id][u] = x+y;
} else if(op[u] == "*") {
dp[id][u] = x*y;
} else if(op[u] == "-") {
dp[id][u] = x-y;
} else {
if(y < 0.012) {
poss[id][u] = 0;
} else dp[id][u] = x/y;
}
}
void printtree(int u) {
if(op[u] == "x") {
cout << op[u];
} else if(op[u] == "sin" || op[u] == "cos") {
cout << op[u] << "(";
printtree(l[u]);
cout << ")";
} else {
cout << "(";
printtree(l[u]);
cout << op[u];
printtree(r[u]);
cout << ")";
}
}
void solve() {
op[0] = "x";
lo[0] = 0;
hi[0] = 1;
for(int i = 1; i <= 9; i++) {
lo[i] = z;
for(int x = lo[i-1]; x < hi[i-1]; x++) {
l[z] = x;
op[z] = "sin";
z++;
l[z] = x;
op[z] = "cos";
z++;
}
for(int j = 0; j <= i-2; j++) {
int k = i-2-j;
for(int x = lo[j]; x < hi[j]; x++) {
for(int y = lo[k]; y < hi[k]; y++) {
l[z] = x;
r[z] = y;
op[z] = "+";
z++;
l[z] = x;
r[z] = y;
op[z] = "-";
z++;
l[z] = x;
r[z] = y;
op[z] = "*";
z++;
l[z] = x;
r[z] = y;
op[z] = "/";
z++;
}
}
}
hi[i] = z;
}
int n;
cin >> n;
// printtree(n);
// return;
// printtree(2);
// cout << endl;
for(int i = 0; i < n; i++) {
cin >> val[i] >> expe[i];
}
for(int j = 0; j < z; j++) {
bool valid = true;
for(int i = 0; i < n; i++) {
calc(i, j);
if(!poss[i][j] || cmp(dp[i][j], expe[i]) != 0) {
valid = false;
}
}
if(valid) {
printtree(j);
cout << endl;
return;
// break;
}
}
// cout << dp[0][2] << endl;
// cout << dp[1][2] << endl;
// cout << dp[2][2] << endl;
// cout << sin(0.61800) << endl;
// cout << dp[0][l[630]] << endl;
// cout << dp[0][l[l[630]]] << endl;
// for(int i = 0; i < n; i++) {
// cout << dp[i][630] << " ?? " << poss[i][630] << endl;
// }
assert(false);
}
int32_t main() {
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(9);
int testes = 1;
// cin >> testes;
int test = 0;
while(testes--) {
// cout << "Case #" << (++test) << ": ";
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 42936kb
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: 11ms
memory: 43864kb
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: 16ms
memory: 42180kb
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