QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#117546 | #6395. Equation Discovering | installb# | TL | 7ms | 3668kb | C++14 | 2.3kb | 2023-07-01 16:28:47 | 2023-07-01 16:28:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
int T;
db x[255],y[255];
int ch[3][255],val[255];
int sonc[8] = {0,2,2,2,2,1,1,0}; // 0 + - * / sin cos x
int tot = 0,cplx = 0;
db chk(int u,db x,int &flg){
if(val[u] == 7) return x;
db ls,rs;
ls = chk(ch[0][u],x,flg);
if(val[u] >= 1 && val[u] <= 4) rs = chk(ch[1][u],x,flg);
if(val[u] == 4 && rs < 0.01) flg = 0;
if(val[u] == 1) return ls + rs;
if(val[u] == 2) return ls - rs;
if(val[u] == 3) return ls * rs;
if(val[u] == 4) return ls / rs;
if(val[u] == 5) return sin(ls);
if(val[u] == 6) return cos(ls);
assert(0);
}
void print(int u){
cout << '(';
if(val[u] == 7) cout << 'x';
if(val[u] == 5) cout << "sin";
if(val[u] == 6) cout << "cos";
if(val[u] >= 1 && val[u] <= 6) print(ch[0][u]);
if(val[u] == 1) cout << "+";
if(val[u] == 2) cout << "-";
if(val[u] == 3) cout << "*";
if(val[u] == 4) cout << "/";
if(val[u] >= 1 && val[u] <= 4) print(ch[1][u]);
cout << ')';
}
void dfs(int u){
// cout << u << ' ' << tot << ' ' << cplx << endl;
// for(int i = 1;i <= tot;i ++) cout << val[i] << ',' << ch[0][i] << ',' << ch[1][i] << " \n"[i == tot];
// cout << endl;
if(u > tot){
int flg = 1;
for(int i = 1;i <= T;i ++){
if(fabs(chk(1,x[i],flg) - y[i]) / max(1.0L,fabs(y[i])) > 1e-3) flg = 0;
}
if(flg){
print(1);
exit(0);
}
return;
}
for(int i = 1;i <= 7;i ++){
if(sonc[i] + cplx > 9) continue;
for(int j = 0;j < sonc[i];j ++) ch[j][u] = ++ tot;
cplx += sonc[i];
val[u] = i;
dfs(u + 1);
val[u] = 0;
tot -= sonc[i];
cplx -= sonc[i];
for(int j = 0;j < sonc[i];j ++) ch[j][u] = 0;
}
}
void solve(){
cin >> T;
for(int i = 1;i <= T;i ++) cin >> x[i] >> y[i];
// for(int i = 1;i <= T;i ++){
// x[i] = i;
// y[i] = sin(x[i]);
// // y[i] = x[i] - sin(cos(x[i])) - cos(x[i]) / x[i];
// }
tot = 1; cplx = 0;
dfs(1);
while(1);
cout << "NO\n";
}
int main(){
ios::sync_with_stdio(false);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 3668kb
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
output:
(((sin(x))-(sin(x)))+((x)*(x)))
result:
ok great!!
Test #2:
score: 0
Accepted
time: 7ms
memory: 3584kb
input:
3 0.618000 1.517072 0.314000 3.132637 1.414000 0.494016
output:
(((x)-(x))+(((sin(x))/(x))/(x)))
result:
ok great!!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3600kb
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))+((x)+(x)))
result:
ok great!!
Test #4:
score: -100
Time Limit Exceeded
input:
5 25.032427 -0.100652 38.727324 1.658518 27.684334 -0.669555 64.282391 8.275303 52.640700 -0.962660