QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117546#6395. Equation Discoveringinstallb#TL 7ms3668kbC++142.3kb2023-07-01 16:28:472023-07-01 16:28:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-01 16:28:50]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:3668kb
  • [2023-07-01 16:28:47]
  • 提交

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

output:


result: