QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#108452 | #6395. Equation Discovering | berarchegas# | WA | 691ms | 32476kb | C++17 | 5.6kb | 2023-05-25 03:07:03 | 2023-05-25 03:07:05 |
Judging History
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] );
}
Details
Tip: Click on the bar to expand more detailed information
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