QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103816#6395. Equation Discoveringskyline#WA 373ms4180kbC++173.0kb2023-05-07 16:59:462023-05-07 16:59:47

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-07 16:59:47]
  • 评测
  • 测评结果:WA
  • 用时:373ms
  • 内存:4180kb
  • [2023-05-07 16:59:46]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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