QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#103816 | #6395. Equation Discovering | skyline# | WA | 373ms | 4180kb | C++17 | 3.0kb | 2023-05-07 16:59:46 | 2023-05-07 16:59:47 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define mp make_pair
#define orz 1000000007
#define fi first
#define se second
#pragma GCC optmize("O2")
#define ld __float128
using namespace std;
int n;
ld x[22],y[22],Y[22],s[22][15];
char S[33];
ld ab(ld x){return (x<0?-x:x);}
string _s[33];
pair<string,ld> ANS[33];
int res;
void prt(int n){
int k=0;
for(int i=1;i<=n;++i){
if(S[i]=='x')_s[++k]="x";
else if(S[i]=='+'||S[i]=='-'||S[i]=='*'||S[i]=='/'){
_s[k-1]='('+_s[k-1]+')'+S[i]+'('+_s[k]+')';
--k;
}
else if(S[i]=='s'){
_s[k]="sin("+_s[k]+')';
}
else{
_s[k]="cos("+_s[k]+')';
}
}
ANS[++res].fi=_s[1];
}
void sol(int c,int ls,int lS){
if(ls==1){
bool ok=1;
for(int i=1;i<=n;++i){
if(ab(s[i][1]-y[i])*Y[i]>0.0005){
ok=0;
break;
}
}
if(ok){
prt(lS);
ANS[res].se=0;
for(int i=1;i<=n;++i)ANS[res].se=max(ANS[res].se,ab(s[i][1]-y[i])*Y[i]);
if(res>=30){
int k=1;
for(int i=2;i<=res;++i)if(ANS[i].se<ANS[k].se)k=i;
for(int i=0;i<ANS[k].fi.size();++i)printf("%c",ANS[k].fi[i]);
printf("\n");
exit(0);
}
}
}
if(ls*2+c<=9){//x
S[lS+1]='x';
for(int i=1;i<=n;++i)s[i][ls+1]=x[i];
sol(c,ls+1,lS+1);
}
if(ls>=2){//+-*/
{//+
S[lS+1]='+';
pair<ld,ld> d[22];
for(int i=1;i<=n;++i)d[i]=mp(s[i][ls-1],s[i][ls]),s[i][ls-1]=s[i][ls-1]+s[i][ls];
sol(c+2,ls-1,lS+1);
for(int i=1;i<=n;++i)s[i][ls-1]=d[i].fi,s[i][ls]=d[i].se;
}
{//-
S[lS+1]='-';
pair<ld,ld> d[22];
for(int i=1;i<=n;++i)d[i]=mp(s[i][ls-1],s[i][ls]),s[i][ls-1]=s[i][ls-1]-s[i][ls];
sol(c+2,ls-1,lS+1);
for(int i=1;i<=n;++i)s[i][ls-1]=d[i].fi,s[i][ls]=d[i].se;
}
{//*
S[lS+1]='*';
pair<ld,ld> d[22];
for(int i=1;i<=n;++i)d[i]=mp(s[i][ls-1],s[i][ls]),s[i][ls-1]=s[i][ls-1]*s[i][ls];
sol(c+2,ls-1,lS+1);
for(int i=1;i<=n;++i)s[i][ls-1]=d[i].fi,s[i][ls]=d[i].se;
}
{///
S[lS+1]='/';
bool ok=1;
for(int i=1;i<=n;++i)if(ab(s[i][ls])<0.16)ok=0,i=n;
if(ok){
pair<ld,ld> d[22];
for(int i=1;i<=n;++i)d[i]=mp(s[i][ls-1],s[i][ls]),s[i][ls-1]=s[i][ls-1]/s[i][ls];
sol(c+2,ls-1,lS+1);
for(int i=1;i<=n;++i)s[i][ls-1]=d[i].fi,s[i][ls]=d[i].se;
}
}
}
if(ls>=1&&c+(ls-1)*2+1<=9){//sc
{
//s
S[lS+1]='s';
ld d[22];
for(int i=1;i<=n;++i)d[i]=s[i][ls],s[i][ls]=sin((double)s[i][ls]);
sol(c+1,ls,lS+1);
for(int i=1;i<=n;++i)s[i][ls]=d[i];
}
{
//c
S[lS+1]='c';
ld d[22];
for(int i=1;i<=n;++i)d[i]=s[i][ls],s[i][ls]=cos((double)s[i][ls]);
sol(c+1,ls,lS+1);
for(int i=1;i<=n;++i)s[i][ls]=d[i];
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
double _x,_y;
scanf("%lf%lf",&_x,&_y);
x[i]=_x,y[i]=_y;
Y[i]=(ld)1.0/max((ld)1.0,ab(y[i]));
}
sol(0,0,0);
int k=1;
for(int i=2;i<=res;++i)if(ANS[i].se<ANS[k].se)k=i;
for(int i=0;i<ANS[k].fi.size();++i)printf("%c",ANS[k].fi[i]);
printf("\n");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4108kb
input:
3 1.000000 1.000000 2.000000 4.000000 3.000000 9.000000
output:
(x)*((x)+((x)*((x)-(x))))
result:
ok great!!
Test #2:
score: 0
Accepted
time: 32ms
memory: 3912kb
input:
3 0.618000 1.517072 0.314000 3.132637 1.414000 0.494016
output:
((sin((x)+((x)-(x))))/(x))/(x)
result:
ok great!!
Test #3:
score: 0
Accepted
time: 4ms
memory: 4104kb
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)+((x)+(x))))
result:
ok great!!
Test #4:
score: 0
Accepted
time: 107ms
memory: 4168kb
input:
5 25.032427 -0.100652 38.727324 1.658518 27.684334 -0.669555 64.282391 8.275303 52.640700 -0.962660
output:
((x)/((x)*(cos(x))))*(sin(x))
result:
ok great!!
Test #5:
score: 0
Accepted
time: 112ms
memory: 3996kb
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: 0
Accepted
time: 35ms
memory: 4180kb
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)-((x)+(x))))))
result:
ok great!!
Test #7:
score: 0
Accepted
time: 157ms
memory: 4000kb
input:
5 3.241091 -32.628130 -83.514144 86.463432 33.586619 40.691607 41.123543 -147.352644 26.896326 27.404018
output:
(x)*((x)/((x)*(sin(x))))
result:
ok great!!
Test #8:
score: -100
Wrong Answer
time: 373ms
memory: 4044kb
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:
result:
wrong output format Unexpected end of file - token expected