QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310292#6395. Equation DiscoveringPlentyOfPenalty#RE 58ms72656kbC++202.7kb2024-01-21 10:32:412024-01-21 10:32:41

Judging History

你现在查看的是最新测评结果

  • [2024-01-21 10:32:41]
  • 评测
  • 测评结果:RE
  • 用时:58ms
  • 内存:72656kb
  • [2024-01-21 10:32:41]
  • 提交

answer

#include<bits/stdc++.h>
#define all(x) begin(x),end(x)
#define double long double
using namespace std;
enum oper{PLUS,MINUS,TIME,DIV,SIN,COS,NONE};
string name[]={"+","-","*","/","sin","cos","x"};
const int N=25;
int n;
double x[N],y[N];
double getdiff(double x,double y){
	return abs(x-y)/max<double>(1,abs(y));
}
struct func{
	oper op;
	string str;
	func *l,*r;
	pair<double,bool> calc(double x){
		if(op==NONE)return {x,false};
		if(PLUS<=op&&op<=DIV){
			auto a=l->calc(x),b=r->calc(x);
			// fprintf(stderr,"!! %.10Lf %d :: %.10Lf %d\n",a.first,a.second,b.first,b.second);
			if(a.second||b.second)return {0,true};
			if(op==DIV){
				if(abs(a.first)<=0.011)return {0,true};
				if(b.second==0)return {0,true};
			}
			if(op==PLUS)a.first+=b.first;
			if(op==MINUS)a.first-=b.first;
			if(op==TIME)a.first*=b.first;
			if(op==DIV)a.first/=b.first;
			// cerr<<"! "<<a.first<<endl;
			if(isnan(a.first)||isinf(a.first)||a.first>1e50||a.first<-1e50)return {0,true};
			return a;
		}
		if(SIN<=op&&op<=COS){
			auto a=l->calc(x);
			if(a.second)return {0,true};
			a.first=op==SIN?sinl(a.first):cosl(a.first);
			if(isnan(a.first)||isinf(a.first)||a.first>1e50||a.first<-1e50)return {0,true};
			return a;
		}
		return {0,true};
	}
};
vector<func> f[10];
int main(){
#ifdef memset0
	freopen("B.in","r",stdin);
#endif
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	f[0].push_back({NONE,"x",nullptr,nullptr});
	for(int k=1;k<=9;k++){
		for(oper op=PLUS;op<=DIV;op=(oper)((int)op+1)){
			for(int i=0;i<=k;i++)
				for(int j=0;j<=k;j++)
					if(i+j+2==k){
						// if(op!=MINUS&&op!=DIV&&i>j)continue;
						for(int x=0;x<f[i].size();x++)
							for(int y=0;y<f[j].size();y++){
								f[k].push_back({
									op,
									"("+f[i][x].str+")"+name[op]+"("+f[j][y].str+")",
									&f[i][x],
									&f[j][y],
								});
							}
					}
		}
		for(oper op=SIN;op<=COS;op=(oper)((int)op+1)){
			for(int x=0;x<f[k-1].size();x++){
				f[k].push_back({
					op,
					name[op]+"("+f[k-1][x].str+")",
					&f[k-1][x],
					nullptr
				});
			}
		}
		// cerr<<k<<" >> "<<f[k].size()<<endl;
		// for(auto x:f[k])cerr<<x.str<<endl;
	}
	for(int k=0;k<=9;k++)
		for(auto fc:f[k]){
			// if(fc.str!="(x)/((x)-(x))")continue;
			bool ok=true;
			for(int i=1;i<=n;i++){
				auto res=fc.calc(x[i]);
				// fprintf(stderr,"%.2Lf %.2Lf => %.10Lf %d\n",x[i],y[i],res.first,res.second);
				if(res.second||isnan(res.first)||isinf(res.first)||(getdiff(res.first,y[i])>3e-4)){
					ok=false;
					break;
				}
			}
			if(ok){
				// cerr<<"k="<<k<<endl;
				cout<<fc.str<<endl;
				return 0;
			}
		}
	assert(0);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 58ms
memory: 72656kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

(x)*(x)

result:

ok great!!

Test #2:

score: -100
Runtime Error

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:


result: