QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104035 | #6395. Equation Discovering | He_Ren# | WA | 245ms | 91516kb | C++14 | 2.4kb | 2023-05-08 12:14:09 | 2023-05-08 12:14:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
typedef pair<int,int> pii;
const int MAXP = 5e5 + 5;
const ldb ldbinf = 1e100;
int pcnt = 0;
int val[MAXP];
string s[MAXP];
char type[MAXP];
vector<int> g[MAXP];
ldb calc(int u,ldb x)
{
if(type[u] == 'x')
return x;
if(type[u] == 's')
{
auto y = calc(g[u][0], x);
return y >= ldbinf / 2? ldbinf: sin(y);
}
if(type[u] == 'c')
{
auto y = calc(g[u][0], x);
return y >= ldbinf / 2? ldbinf: cos(y);
}
auto l = calc(g[u][0], x);
auto r = calc(g[u][1], x);
if(l >= ldbinf / 2 || r >= ldbinf / 2)
return NAN;
if(type[u] == '+') return l + r;
if(type[u] == '-') return l - r;
if(type[u] == '*') return l * r;
if(type[u] == '/') return fabs(r) >= 0.01? l / r: ldbinf;
return NAN;
}
int main(void)
{
set<string> bak;
auto push = [&] (int fir,string sec) -> int
{
if(bak.emplace(sec).second)
{
int u = ++pcnt;
val[u] = fir;
s[u] = sec;
return u;
}
return 0;
};
auto chk1 = [&] (int u)
{
if(val[u] + 1 > 9) return;
int v;
v = push(val[u] + 1, "sin(" + s[u] + ")");
if(v)
{
type[v] = 's';
g[v] = {u};
}
v = push(val[u] + 1, "cos(" + s[u] + ")");
if(v)
{
type[v] = 'c';
g[v] = {u};
}
};
auto chk2 = [&] (int l,int r)
{
if(val[l] + val[r] + 2 > 9) return;
const string oper = "+-*/";
for(auto t: oper)
{
if((t == '+' || t == '*') && s[l] > s[r]) continue;
int v = push(val[l] + val[r] + 2, "(" + s[l] + t + s[r] + ")");
if(v)
{
type[v] = t;
g[v] = {l,r};
}
}
};
push(0, "x");
type[1] = 'x';
vector< vector<int> > vec(10);
for(int u=1; u<=pcnt; ++u)
{
chk1(u);
vec[val[u]].emplace_back(u);
for(int i=0; i<=9 && val[u] + i + 2 <= 9; ++i)
for(auto oth: vec[i])
{
chk2(u, oth);
chk2(oth, u);
}
}
int n;
cin >> n;
vector< array<ldb,2> > p(n);
for(auto &t: p)
cin >> t[0] >> t[1];
for(int i=1; i<=pcnt; ++i)
{
bool flag = 1;
for(int j=0; j<n; ++j)
{
ldb x = p[j][0], y = p[j][1];
auto cur = calc(i, x);
if(cur >= ldbinf / 2)
{
flag = 0;
break;
}
if(fabs(cur - y) / max((ldb)1, y) > 1e-3)
{
flag = 0;
break;
}
}
if(flag)
{
cout << s[i] << endl;
return 0;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 245ms
memory: 91428kb
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: 235ms
memory: 91416kb
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: 230ms
memory: 91336kb
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: 223ms
memory: 91408kb
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: 229ms
memory: 91516kb
input:
5 78.611917 -0.992212 -29.857271 1.011993 -75.513655 1.006611 68.512394 1.145128 7.961096 0.881661
output:
((sin(x)*sin(x))+cos(x))
result:
ok great!!
Test #6:
score: -100
Wrong Answer
time: 230ms
memory: 91412kb
input:
5 -78.733375 0.503570 -20.187183 0.735779 -38.984992 0.730890 47.859232 0.622831 -19.657164 0.641512
output:
((x/(x-x))+x)
result:
wrong answer div a small number