QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#150738 | #6395. Equation Discovering | aesthetic# | WA | 570ms | 4220kb | C++14 | 3.2kb | 2023-08-26 05:33:27 | 2023-08-26 05:33:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 22;
int n;
double x[MAXN], y[MAXN];
vector<char> ops;
string genExpr(vector<char> ops)
{
vector<string> a;
while(!ops.empty())
{
char c = ops.back();
if(c == 'x')
{
a.push_back("x");
}
else if(c == '+' || c == '-' || c == '*' || c == '/')
{
string z = a.back();
a.pop_back();
string w = a.back();
a.pop_back();
if(c == '+')
a.push_back("(" + z + "+" + w + ")");
else if(c == '-')
a.push_back("(" + z + "-" + w + ")");
else if(c == '*')
a.push_back("(" + z + "*" + w + ")");
else if(c == '/')
a.push_back("(" + z + "/" + w + ")");
}
else if(c == 's' || c == 'c')
{
string z = a.back();
a.pop_back();
if(c == 's')
a.push_back("sin(" + z + ")");
else if(c == 'c')
a.push_back("cos(" + z + ")");
}
ops.pop_back();
}
return a.back();
}
bool getOut(vector<char> ops, double x, double &ret)
{
vector<double> a;
while(!ops.empty())
{
char c = ops.back();
if(c == 'x')
{
a.push_back(x);
}
else if(c == '+' || c == '-' || c == '*' || c == '/')
{
if(a.size() < 2)
return false;
double z = a.back();
a.pop_back();
double w = a.back();
a.pop_back();
if(c == '+')
a.push_back(z + w);
else if(c == '-')
a.push_back(z - w);
else if(c == '*')
a.push_back(z * w);
else if(c == '/')
{
if(w < 0.001)
return false;
a.push_back(z / w);
}
}
else if(c == 's' || c == 'c')
{
if(a.size() < 1)
return false;
double z = a.back();
a.pop_back();
if(c == 's')
a.push_back(sin(z));
else if(c == 'c')
a.push_back(cos(z));
}
ops.pop_back();
}
if(a.size() != 1)
return false;
ret = a.back();
return true;
}
bool check()
{
if(ops.empty())
return false;
for(int i = 1; i <= n; ++i)
{
double yy;
if(!getOut(ops, x[i], yy))
return false;
if(abs(yy - y[i]) >= 1e-5)
return false;
}
return true;
}
bool validatePrefix(vector<char> ops)
{
int cnt = 0;
for(int i = 0; i < ops.size(); ++i)
{
char c = ops[i];
if(c == 'x')
cnt++;
else if(c == '+' || c == '-' || c == '*' || c == '/')
cnt--;
if(cnt > 1)
return false;
}
return true;
}
int cost = 0, xs = 0;
void go()
{
if(cost > 9 || xs > 5)
return;
// cout << "Trying: ";
// for(char c : ops)
// cout << c << ' ';
// cout << endl;
if(!validatePrefix(ops))
return;
if(check())
{
// for(char c : ops)
// cout << c << ' ';
// cout << endl;
cout << genExpr(ops) << endl;
exit(0);
}
for(char c : {'x', '+', '-', '*', 's', 'c', '/'})
{
ops.push_back(c);
if(c == '+' || c == '-' || c == '*' || c == '/')
cost += 2;
else if(c == 'c' || c == 's')
cost++;
else if(c == 'x')
xs++;
go();
if(c == '+' || c == '-' || c == '*' || c == '/')
cost -= 2;
else if(c == 'c' || c == 's')
cost--;
else if(c == 'x')
xs--;
ops.pop_back();
}
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
cin >> n;
for(int i = 1; i <= n; ++i)
cin >> x[i] >> y[i];
go();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 127ms
memory: 4020kb
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
output:
(x+((x*x)-x))
result:
ok great!!
Test #2:
score: 0
Accepted
time: 123ms
memory: 4220kb
input:
3 0.618000 1.517072 0.314000 3.132637 1.414000 0.494016
output:
(x+((sin(x)/(x*x))-x))
result:
ok great!!
Test #3:
score: 0
Accepted
time: 161ms
memory: 4100kb
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: -100
Wrong Answer
time: 570ms
memory: 4116kb
input:
5 25.032427 -0.100652 38.727324 1.658518 27.684334 -0.669555 64.282391 8.275303 52.640700 -0.962660
output:
result:
wrong output format Unexpected end of file - token expected