QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#310285 | #6395. Equation Discovering | PlentyOfPenalty# | WA | 64ms | 74452kb | C++20 | 2.5kb | 2024-01-21 10:21:06 | 2024-01-21 10:21:07 |
Judging History
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(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))return {0,true};
return a;
}
if(SIN<=op&&op<=COS){
auto a=l->calc(x);
a.first=op==SIN?sinl(a.first):cosl(a.first);
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: 51ms
memory: 73164kb
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: 62ms
memory: 73300kb
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: 58ms
memory: 74452kb
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: 64ms
memory: 72832kb
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: -100
Wrong Answer
time: 50ms
memory: 74400kb
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)/((x)-(x)))
result:
wrong answer div a small number