QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105218#6395. Equation DiscoveringSommohitoTL 14ms6448kbC++204.3kb2023-05-13 17:11:092023-05-13 17:11:13

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-13 17:11:13]
  • 评测
  • 测评结果:TL
  • 用时:14ms
  • 内存:6448kb
  • [2023-05-13 17:11:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 2e5 +5;
typedef pair<int,int> pii;

//int cnt(int comp)
//{
//    ll ans=0;
//
//    if(comp-2>=0)
//    {
//        int baki=comp-2;
//        for(int l=0;l<=baki;l++)
//        {
//            int L=cnt(l);
//            int R=cnt(baki-l);
//            ans+=L*R*4;
//        }
//    }
//    if(comp-1>=0)
//    {
//        ans+=cnt(comp-1)*2;
//    }
//    ans++;
//
//    return ans;
//}
class S;
bool F;

class S
{
    public:
    string op;
    S * lft;
    S * right;

    ld eval(ld x)
    {
        if(op=="+") return lft->eval(x)+right->eval(x);
        if(op=="-") return lft->eval(x)-right->eval(x);
        if(op=="*") return lft->eval(x)*right->eval(x);
        if(op=="/")
        {
            if(abs(right->eval(x))<0.01) F=1;
            return lft->eval(x)/right->eval(x);
        }
        if(op=="sin") return sin(lft->eval(x));
        if(op=="cos") return cos(lft->eval(x));
        if(op=="x") return x;
    }
    string make()
    {
        if(op=="+") return "("+lft->make()+"+"+right->make()+")";
        if(op=="-") return "("+lft->make()+"-"+right->make()+")";
        if(op=="*") return "("+lft->make()+"*"+right->make()+")";
        if(op=="/") return "("+lft->make()+"/"+right->make()+")";
        if(op=="sin") return "sin("+lft->make()+")";
        if(op=="cos") return "cos("+lft->make()+")";
        if(op=="x") return "x";
    }
};

vector<ld> x,y;
vector<S*> save[10];
int dp[10];
int n;

vector<S*> cnt(int comp)
{
    if(dp[comp])
        return save[comp];
    dp[comp]=true;

    vector<S*> ans;

    if(comp-2>=0)
    {
        int baki=comp-2;
        for(int l=0; l<=baki; l++)
        {
            auto L=cnt(l);
            auto R=cnt(baki-l);
            for(auto &l:L)
            {
                for(auto &r:R)
                {
                    {
                        S * notun = new S();
                        notun->op="+";
                        notun->lft=l;
                        notun->right=r;
                        ans.push_back(notun);
                    }
                    {
                        S * notun = new S();
                        notun->op="-";
                        notun->lft=l;
                        notun->right=r;
                        ans.push_back(notun);
                    }
                    {
                        S * notun = new S();
                        notun->op="*";
                        notun->lft=l;
                        notun->right=r;
                        ans.push_back(notun);
                    }

                    {
                        S * notun = new S();
                        notun->op="/";
                        notun->lft=l;
                        notun->right=r;
                        ans.push_back(notun);
                    }
                }
            }
        }
    }
    if(comp-1>=0)
    {
        auto L=cnt(comp-1);

        for(auto &l:L)
        {
            {
                S * notun = new S();
                notun->op="sin";
                notun->lft=l;
                ans.push_back(notun);
            }
            {
                S * notun = new S();
                notun->op="cos";
                notun->lft=l;
                ans.push_back(notun);
            }
        }

    }
    S * notun = new S();
    notun->op="x";
    ans.push_back(notun);

    return save[comp]=ans;
}
void TEST_CASES()
{
     cin>>n;
//    n=2;
    x.resize(n);
    y.resize(n);
    for(int i=0; i<n; i++)
    {
        cin>>x[i]>>y[i];
//        x[i]=1e3-(i+1);
//        y[i]=sin(x[i])*cos(x[i]);
    }

    for(int comp=0;comp<=9;comp++)
    {
        auto got=cnt(comp);
        for(auto r:got)
        {
            bool f=1;
            for(int i=0;i<n;i++)
            {
                F=0;
                if(abs(r->eval(x[i])-y[i])>1e-3||F==1) f=0;

            }
            if(f)
            {
                cout<<r->make();
                exit(0);
            }
        }
    }
}




/*
*/

int32_t main()
{
#ifndef APURBA
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    //freopen("input->txt","r",stdin);
    //freopen("out1->txt","w",stdout);
    int t=1;
    //cin>>t;
    while(t--)
    {
        TEST_CASES();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3600kb

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: 0ms
memory: 3744kb

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: 3620kb

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: 1ms
memory: 3544kb

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:

(sin(x)/cos(x))

result:

ok great!!

Test #5:

score: 0
Accepted
time: 14ms
memory: 6448kb

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: 2ms
memory: 3672kb

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: 2ms
memory: 3592kb

input:

5
3.241091 -32.628130
-83.514144 86.463432
33.586619 40.691607
41.123543 -147.352644
26.896326 27.404018

output:

(x/sin(x))

result:

ok great!!

Test #8:

score: -100
Time Limit Exceeded

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: