QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108466#6395. Equation Discoveringberarchegas#WA 1966ms27668kbC++1713.3kb2023-05-25 04:07:152023-05-25 04:07:16

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-25 04:07:16]
  • 评测
  • 测评结果：WA
  • 用时：1966ms
  • 内存：27668kb
查看
  • [2023-05-25 04:07:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int maxn = 50;

int n;

double x[maxn], y[maxn];

vector<string> expressions[10];

string add(string s)
{
    if( s == "x" )
        return s;

    return "(" + s + ")";
}

void generateExpressions()
{
    expressions[0].push_back( "x" );

    expressions[1].push_back( "sin(x)" );
    expressions[1].push_back( "cos(x)" );

    expressions[2].push_back( "sin(sin(x))" );
    expressions[2].push_back( "sin(cos(x))" );
    expressions[2].push_back( "cos(sin(x))" );
    expressions[2].push_back( "cos(cos(x))" );
    expressions[2].push_back( "x+x" );
    expressions[2].push_back( "x-x" );
    expressions[2].push_back( "x*x" );
    expressions[2].push_back( "x/x" );

    expressions[3].push_back( "sin(sin(sin(x)))" );
    expressions[3].push_back( "sin(sin(cos(x)))" );
    expressions[3].push_back( "sin(cos(sin(x)))" );
    expressions[3].push_back( "sin(cos(cos(x)))" );
    expressions[3].push_back( "sin(x+x)" );
    expressions[3].push_back( "sin(x-x)" );
    expressions[3].push_back( "sin(x*x)" );
    expressions[3].push_back( "sin(x/x)" );
    expressions[3].push_back( "cos(sin(sin(x)))" );
    expressions[3].push_back( "cos(sin(cos(x)))" );
    expressions[3].push_back( "cos(cos(sin(x)))" );
    expressions[3].push_back( "cos(cos(cos(x)))" );
    expressions[3].push_back( "cos(x+x)" );
    expressions[3].push_back( "cos(x-x)" );
    expressions[3].push_back( "cos(x*x)" );
    expressions[3].push_back( "cos(x/x)" );
    expressions[3].push_back( "x+sin(x)" );
    expressions[3].push_back( "x+cos(x)" );
    expressions[3].push_back( "x*sin(x)" );
    expressions[3].push_back( "x*cos(x)" );
    expressions[3].push_back( "x/sin(x)" );
    expressions[3].push_back( "x/cos(x)" );
    expressions[3].push_back( "x-sin(x)" );
    expressions[3].push_back( "x-cos(x)" );
    expressions[3].push_back( "sin(x)/x" );
    expressions[3].push_back( "cos(x)/x" );
    expressions[3].push_back( "sin(x)-x" );
    expressions[3].push_back( "cos(x)-x" );

    expressions[4].push_back( "sin(sin(sin(sin(x))))" );
    expressions[4].push_back( "sin(sin(sin(cos(x))))" );
    expressions[4].push_back( "sin(sin(cos(sin(x))))" );
    expressions[4].push_back( "sin(sin(cos(cos(x))))" );
    expressions[4].push_back( "sin(sin(x+x))" );
    expressions[4].push_back( "sin(sin(x-x))" );
    expressions[4].push_back( "sin(sin(x*x))" );
    expressions[4].push_back( "sin(sin(x/x))" );
    expressions[4].push_back( "sin(cos(sin(sin(x))))" );
    expressions[4].push_back( "sin(cos(sin(cos(x))))" );
    expressions[4].push_back( "sin(cos(cos(sin(x))))" );
    expressions[4].push_back( "sin(cos(cos(cos(x))))" );
    expressions[4].push_back( "sin(cos(x+x))" );
    expressions[4].push_back( "sin(cos(x-x))" );
    expressions[4].push_back( "sin(cos(x*x))" );
    expressions[4].push_back( "sin(cos(x/x))" );
    expressions[4].push_back( "sin(x+sin(x))" );
    expressions[4].push_back( "sin(x+cos(x))" );
    expressions[4].push_back( "sin(x*sin(x))" );
    expressions[4].push_back( "sin(x*cos(x))" );
    expressions[4].push_back( "sin(x/sin(x))" );
    expressions[4].push_back( "sin(x/cos(x))" );
    expressions[4].push_back( "sin(x-sin(x))" );
    expressions[4].push_back( "sin(x-cos(x))" );
    expressions[4].push_back( "sin(sin(x)/x)" );
    expressions[4].push_back( "sin(cos(x)/x)" );
    expressions[4].push_back( "sin(sin(x)-x)" );
    expressions[4].push_back( "sin(cos(x)-x)" );
    expressions[4].push_back( "cos(sin(sin(sin(x))))" );
    expressions[4].push_back( "cos(sin(sin(cos(x))))" );
    expressions[4].push_back( "cos(sin(cos(sin(x))))" );
    expressions[4].push_back( "cos(sin(cos(cos(x))))" );
    expressions[4].push_back( "cos(sin(x+x))" );
    expressions[4].push_back( "cos(sin(x-x))" );
    expressions[4].push_back( "cos(sin(x*x))" );
    expressions[4].push_back( "cos(sin(x/x))" );
    expressions[4].push_back( "cos(cos(sin(sin(x))))" );
    expressions[4].push_back( "cos(cos(sin(cos(x))))" );
    expressions[4].push_back( "cos(cos(cos(sin(x))))" );
    expressions[4].push_back( "cos(cos(cos(cos(x))))" );
    expressions[4].push_back( "cos(cos(x+x))" );
    expressions[4].push_back( "cos(cos(x-x))" );
    expressions[4].push_back( "cos(cos(x*x))" );
    expressions[4].push_back( "cos(cos(x/x))" );
    expressions[4].push_back( "cos(x+sin(x))" );
    expressions[4].push_back( "cos(x+cos(x))" );
    expressions[4].push_back( "cos(x*sin(x))" );
    expressions[4].push_back( "cos(x*cos(x))" );
    expressions[4].push_back( "cos(x/sin(x))" );
    expressions[4].push_back( "cos(x/cos(x))" );
    expressions[4].push_back( "cos(x-sin(x))" );
    expressions[4].push_back( "cos(x-cos(x))" );
    expressions[4].push_back( "cos(sin(x)/x)" );
    expressions[4].push_back( "cos(cos(x)/x)" );
    expressions[4].push_back( "cos(sin(x)-x)" );
    expressions[4].push_back( "cos(cos(x)-x)" );
    expressions[4].push_back( "x+sin(sin(x))" );
    expressions[4].push_back( "x+sin(cos(x))" );
    expressions[4].push_back( "x+cos(sin(x))" );
    expressions[4].push_back( "x+cos(cos(x))" );
    expressions[4].push_back( "x+(x+x)" );
    expressions[4].push_back( "x+(x*x)" );
    expressions[4].push_back( "x+(x/x)" );
    expressions[4].push_back( "x*sin(sin(x))" );
    expressions[4].push_back( "x*sin(cos(x))" );
    expressions[4].push_back( "x*cos(sin(x))" );
    expressions[4].push_back( "x*cos(cos(x))" );
    expressions[4].push_back( "x*(x+x)" );
    expressions[4].push_back( "x*(x-x)" );
    expressions[4].push_back( "x*(x*x)" );
    expressions[4].push_back( "x*(x/x)" );
    expressions[4].push_back( "x/sin(sin(x))" );
    expressions[4].push_back( "x/sin(cos(x))" );
    expressions[4].push_back( "x/cos(sin(x))" );
    expressions[4].push_back( "x/cos(cos(x))" );
    expressions[4].push_back( "x/(x+x)" );
    expressions[4].push_back( "x/(x*x)" );
    expressions[4].push_back( "x/(x/x)" );
    expressions[4].push_back( "x-sin(sin(x))" );
    expressions[4].push_back( "x-sin(cos(x))" );
    expressions[4].push_back( "x-cos(sin(x))" );
    expressions[4].push_back( "x-cos(cos(x))" );
    expressions[4].push_back( "x-(x+x)" );
    expressions[4].push_back( "x-(x*x)" );
    expressions[4].push_back( "x-(x/x)" );
    expressions[4].push_back( "sin(x)+sin(x)" );
    expressions[4].push_back( "sin(x)+cos(x)" );
    expressions[4].push_back( "cos(x)+cos(x)" );
    expressions[4].push_back( "sin(x)*sin(x)" );
    expressions[4].push_back( "sin(x)*cos(x)" );
    expressions[4].push_back( "cos(x)*cos(x)" );
    expressions[4].push_back( "sin(x)/cos(x)" );
    expressions[4].push_back( "cos(x)/sin(x)" );
    expressions[4].push_back( "sin(x)-cos(x)" );
    expressions[4].push_back( "cos(x)-sin(x)" );
    expressions[4].push_back( "sin(sin(x))/x" );
    expressions[4].push_back( "sin(cos(x))/x" );
    expressions[4].push_back( "cos(sin(x))/x" );
    expressions[4].push_back( "cos(cos(x))/x" );
    expressions[4].push_back( "(x+x)/x" );
    expressions[4].push_back( "(x-x)/x" );
    expressions[4].push_back( "(x*x)/x" );
    expressions[4].push_back( "(x/x)/x" );
    expressions[4].push_back( "sin(sin(x))-x" );
    expressions[4].push_back( "sin(cos(x))-x" );
    expressions[4].push_back( "cos(sin(x))-x" );
    expressions[4].push_back( "cos(cos(x))-x" );
    expressions[4].push_back( "(x+x)-x" );
    expressions[4].push_back( "(x-x)-x" );
    expressions[4].push_back( "(x*x)-x" );
    expressions[4].push_back( "(x/x)-x" );


    for(int cost = 5 ; cost <= 9 ; cost++)
    {
        for(string x: expressions[cost - 1])
            expressions[cost].push_back( "sin(" + x + ")" );

        for(string x: expressions[cost - 1])
            expressions[cost].push_back( "cos(" + x + ")" );

        for(int costLeft = 0 ; costLeft <= cost - 2 ; costLeft++)
        {
            int costRight = (cost - 2) - costLeft;

            // Soma
            if( costLeft < costRight )
            {
                for(string L: expressions[costLeft])
                    for(string R: expressions[costRight])
                        expressions[cost].push_back( add(L) + "+" + add(R) );
            }
            else if( costLeft == costRight )
            {
                for(int a = 0 ; a < (int)expressions[costLeft].size() ; a++)
                    for(int b = a ; b < (int)expressions[costLeft].size() ; b++)
                        expressions[cost].push_back( add(expressions[costLeft][a]) + "+" + add(expressions[costLeft][b]) );
            }

            // Multiplicacao
            if( costLeft < costRight )
            {
                for(string L: expressions[costLeft])
                    for(string R: expressions[costRight])
                        expressions[cost].push_back( add(L) + "*" + add(R) );
            }
            else if( costLeft == costRight )
            {
                for(int a = 0 ; a < (int)expressions[costLeft].size() ; a++)
                    for(int b = a ; b < (int)expressions[costLeft].size() ; b++)
                        expressions[cost].push_back( add(expressions[costLeft][a]) + "*" + add(expressions[costLeft][b]) );
            }

            // Divisao
            for(int a = 0 ; a < (int)expressions[costLeft].size() ; a++)
                for(int b = 0 ; b < (int)expressions[costRight].size() ; b++)
                    if( a != b || costLeft != costRight ) expressions[cost].push_back( add(expressions[costLeft][a]) + "/" + add(expressions[costRight][b]) );

            // Divisao
            for(int a = 0 ; a < (int)expressions[costLeft].size() ; a++)
                for(int b = 0 ; b < (int)expressions[costRight].size() ; b++)
                    if( a != b || costLeft != costRight ) expressions[cost].push_back( add(expressions[costLeft][a]) + "-" + add(expressions[costRight][b]) );
        }

        // if( cost == 4 )
        // {
        //     for(string x: expressions[4])
        //         cout << x << endl;
        // }
    }
}

double eps = 0.001;

bool areEqual(double f, double y) {
    return abs(f - y)/max(1.0, abs(y)) <= eps/2;
}

bool isValid(string& expr, double x, double y)
{
    if( expr == "x" )
        return areEqual( x , y );

    vector<double> values;
    vector<char> operations;

    vector<int> idBracket;
    vector<int> idOperation;

    for(int i = 0 ; i < (int)expr.size() ; i++)
    {
        if( expr[i] == '(' )
        {
            idBracket.push_back( i );
            continue;
        }

        if( expr[i] == 'x' )
        {
            values.push_back( x );
            continue;
        }

        if( expr[i] == 's' || expr[i] == 'c' )
        {
            idBracket.push_back( i + 3 );
            idOperation.push_back( i + 3 );

            operations.push_back( expr[i] );

            i += 3;

            continue;
        }

        if( expr[i] == '+' || expr[i] == '-' || expr[i] == '*' || expr[i] == '/' )
        {
            idOperation.push_back( i );
            operations.push_back( expr[i] );

            continue;
        }

        if( expr[i] == ')' )
        {
            if( idOperation.empty() || idOperation.back() < idBracket.back() )
            {
                idBracket.pop_back();
                continue;
            }

            char op = operations.back();
            operations.pop_back();

            idBracket.pop_back();
            idOperation.pop_back();

            if( op == 's' || op == 'c' )
            {
                double v = values.back();
                values.pop_back();

                if( op == 's' )
                    values.push_back( sin(v) );
                else
                    values.push_back( cos(v) );
            }
            else
            {
                double a = values.back(); values.pop_back();
                double b = values.back(); values.pop_back();
                swap( a , b );

                // cout << "entrei " << a << " " << op << " " << b << endl;

                if( op == '/' && areEqual( b , 0 ) )
                    return false;

                if( op == '+' )
                    values.push_back( a + b );

                if( op == '-' )
                    values.push_back( a - b );

                if( op == '*' )
                    values.push_back( a * b );

                if( op == '/' )
                    values.push_back( a / b );
            }
        }
    }

    // cout << fixed << setprecision(12);
    // cout << expr << " " << x << " = " << values.back() << endl;
    // cout << y << endl;

    return areEqual( values.back() , y );
}

int main()
{
    generateExpressions();

    cin >> n;

    for(int i = 1 ; i <= n ; i++)
        cin >> x[i] >> y[i];

    for(int cost = 0 ; cost <= 9 ; cost++)
    {
        for(string expr: expressions[cost])
        {
            bool isGood = true;
            expr = add(expr);

            for(int i = 1 ; i <= n ; i++)
                if( !isValid( expr , x[i] , y[i] ) ) isGood = false;

            if( isGood )
            {
                cout << expr << endl;
                return 0;
            }
        }
    }

    // string s = "((sin(x))/((x)*(x)))";

    // for(int i = 1 ; i <= n ; i++)
    //     isValid( s , x[i] , y[i] );

    // isValid( s , x[1] , y[1] );
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 46ms
memory: 27580kb

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: 47ms
memory: 27508kb

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: 47ms
memory: 27516kb

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: 38ms
memory: 27584kb

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: 61ms
memory: 27576kb

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: 42ms
memory: 27516kb

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: 31ms
memory: 27508kb

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: 0
Accepted
time: 601ms
memory: 27576kb

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:

(sin(sin(x/(sin(x/(x*x))))))

result:

ok great!!

Test #9:

score: 0
Accepted
time: 365ms
memory: 27596kb

input:

20
76.797930 0.000002
-76.263778 -0.000002
55.449039 0.000006
10.462093 0.000873
-78.051671 -0.000002
-52.781249 -0.000007
47.053973 0.000010
96.629212 0.000001
-40.697847 -0.000015
31.141805 0.000033
-87.087384 -0.000002
-54.709885 -0.000006
-65.741847 -0.000004
-87.430820 -0.000001
9.420126 0.0011...

output:

(x/(x*(x*(x*x))))

result:

ok great!!

Test #10:

score: 0
Accepted
time: 49ms
memory: 27508kb

input:

20
24.490647 23.891773
17.327799 16.329001
21.204241 21.912414
83.489542 84.461510
-55.546573 -54.703972
-7.608368 -8.578356
-3.286697 -3.142101
-66.606831 -66.014954
-44.896454 -45.688502
97.541741 97.389961
-59.986043 -59.694554
57.723989 58.646803
-99.857351 -99.233536
29.134673 28.376609
-98.668...

output:

(x+sin(x))

result:

ok great!!

Test #11:

score: 0
Accepted
time: 44ms
memory: 27512kb

input:

20
89.594917 88.596688
-45.187625 -44.253669
97.451471 97.513530
35.078537 35.576300
82.504351 81.771201
-49.755211 -50.243625
-23.019693 -23.876242
-45.247155 -44.293590
75.324114 75.398156
78.533049 78.526282
99.112156 100.100628
31.983437 31.445903
71.251578 70.407388
-44.178279 -43.983549
-25.28...

output:

(x-sin(x))

result:

ok great!!

Test #12:

score: 0
Accepted
time: 53ms
memory: 27668kb

input:

20
16.664144 7.850741
44.708237 22.196248
-10.852343 1.533223
-42.713221 -12.119419
-27.815914 -11.038511
31.908696 13.299065
-82.394044 40.761558
-37.317157 -12.907073
-35.369997 17.659068
93.569121 -45.722539
-30.589159 -15.242258
16.180069 6.553209
56.572831 1.366451
99.591187 -47.440823
12.73229...

output:

(x*(sin(x)*cos(x)))

result:

ok great!!

Test #13:

score: 0
Accepted
time: 50ms
memory: 27512kb

input:

20
-583.519562 0.000000
-169.653469 0.000000
372.798856 0.000000
180.084282 0.000000
139.388742 0.000000
-648.300263 0.000000
-859.523046 0.000000
-267.278551 0.000000
635.554372 0.000000
299.925737 0.000000
-628.299469 0.000000
169.393099 0.000000
556.144161 0.000000
-881.876627 0.000000
328.692044...

output:

(x-x)

result:

ok great!!

Test #14:

score: 0
Accepted
time: 31ms
memory: 27568kb

input:

20
746.491049 746.491049
414.031997 414.031997
-975.051138 -975.051138
45.313068 45.313068
-181.090458 -181.090458
119.607074 119.607074
245.794647 245.794647
-794.156219 -794.156219
461.647608 461.647608
-392.604379 -392.604379
384.522118 384.522118
-461.749513 -461.749513
766.462890 766.462890
244...

output:

x

result:

ok great!!

Test #15:

score: 0
Accepted
time: 53ms
memory: 27504kb

input:

20
4.278335 0.092599
3.559350 0.559919
-2.517239 0.403581
-0.955317 0.182475
3.048015 0.888213
-0.638367 0.393205
-2.188885 0.183959
-0.367275 0.597938
1.106453 0.948186
0.339096 0.971773
-0.678258 0.364003
4.364111 0.060002
-0.671364 0.369012
-2.777257 0.600136
1.617698 0.909755
-3.400784 0.950952
...

output:

(sin((sin(x))+(x/x)))

result:

ok great!!

Test #16:

score: 0
Accepted
time: 1966ms
memory: 27508kb

input:

20
3.692126 -0.260752
0.663419 1.200876
1.167172 0.874743
4.852602 0.631308
3.373109 -0.334749
4.749943 0.529545
-2.549440 -0.245748
-1.158832 0.881804
4.115764 -0.040747
-3.401216 -0.330886
-4.320685 0.119451
-0.070540 1.332133
-4.666465 0.446117
-4.720184 0.499803
-1.731319 0.332854
4.232513 0.046...

output:

((sin(cos(x)))+(sin(sin(cos(x/x)))))

result:

ok great!!

Test #17:

score: 0
Accepted
time: 605ms
memory: 27568kb

input:

20
1.462467 0.804429
-2.922001 0.192241
4.580542 -0.620639
-0.475001 -0.799291
-1.988595 -0.234001
1.262913 0.840075
-3.176510 -0.034797
2.030387 0.180297
-3.244547 -0.099928
-3.321420 -0.164361
-0.538138 -0.818609
2.485817 -0.209990
-0.282936 -0.652106
0.964792 0.840607
-1.300754 -0.837872
4.323400...

output:

(sin(sin((sin(x))+(sin(sin(x+x))))))

result:

ok great!!

Test #18:

score: -100
Wrong Answer
time: 59ms
memory: 27448kb

input:

20
-1.290592 0.818752
0.639318 0.516086
-4.576452 0.791075
2.349231 0.829843
3.053369 0.646833
-4.276424 0.836563
-4.295090 0.835111
1.704429 0.790551
1.694925 0.788364
0.763954 0.527671
-0.477936 0.769603
0.395468 0.525360
0.686854 0.519231
-1.940048 0.637497
2.188388 0.840879
1.028990 0.584344
3.9...

output:

(sin(cos(sin(x+(x/x)))))

result:

wrong answer div a small number
English 繁體中文 简体中文

Server Time: 2024-12-02 23:32:16 | OpenSource Project