QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#108452#6395. Equation Discoveringberarchegas#WA 691ms32476kbC++175.6kb2023-05-25 03:07:032023-05-25 03:07:05

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 03:07:05]
  • 评测
  • 测评结果:WA
  • 用时:691ms
  • 内存:32476kb
  • [2023-05-25 03:07:03]
  • 提交

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) { return "(" + s + ")"; }

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

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

    for(int cost = 2 ; 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;

            if( costLeft <= costRight )
            {
                for(string L: expressions[costLeft])
                    for(string R: expressions[costRight])
                        expressions[cost].push_back( add(L) + "+" + add(R) );

                for(string L: expressions[costLeft])
                    for(string R: expressions[costRight])
                        expressions[cost].push_back( add(L) + "*" + add(R) );
            }

            for(string L: expressions[costLeft])
                for(string R: expressions[costRight])
                    expressions[cost].push_back( add(L) + "-" + add(R) );

            for(string L: expressions[costLeft])
                for(string R: expressions[costRight])
                    expressions[cost].push_back( add(L) + "/" + add(R) );
        }
    }
}

const double eps = 1e-2;

bool areEqual(double x, double y) {
    return (x + eps > y && x - eps < y);
}

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++)
    {
        // cout << "-------------------- To no " << i << endl;

        // cout << "values = ";

        // for(auto x: values)
        //     cout << x << " ";

        // cout << endl;
        // cout << "operations = ";

        // for(auto x: operations)
        //     cout << x << " ";

        // cout << endl;
        // cout << "idBracket = ";

        // for(auto x: idBracket)
        //     cout << x << " ";

        // cout << endl;
        // cout << "idOperation = ";

        // for(auto x: idOperation)
        //     cout << x << " ";

        // cout << endl;
        // cout << endl;

        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);

            // cout << expr << endl;

            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] );
}

详细

Test #1:

score: 100
Accepted
time: 48ms
memory: 32456kb

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: 53ms
memory: 32384kb

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

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: 58ms
memory: 32244kb

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: 72ms
memory: 32476kb

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: 48ms
memory: 32288kb

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: 44ms
memory: 32376kb

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: 691ms
memory: 32472kb

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: -100
Wrong Answer
time: 135ms
memory: 32448kb

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:

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

result:

wrong answer fail to discover