QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#135675 | #6395. Equation Discovering | UrgantTeam | WA | 1380ms | 160168kb | C++23 | 6.6kb | 2023-08-05 21:26:54 | 2023-08-05 21:26:55 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second
using namespace std;
typedef long double ld;
typedef long long ll;
const ld EPS = 0.005;
const ld EPS_RES = 1e-4;
struct Node
{
int opcode;
int son[2];
};
ld valx[25], valy[25];
ld result[25][1005];
vector <vector <Node> > generate_expr(int deep, int state)
{
if (state == 0)
{
return generate_expr(deep, 1);
}
if (state == 1)
{
vector <vector <Node> > A = generate_expr(deep, 2);
for (int lef = 0; lef <= deep - 2; lef++)
{
int rig = deep - 2 - lef;
vector <vector <Node> > B = generate_expr(lef, 0);
vector <vector <Node> > C = generate_expr(rig, 0);
for (const auto &x : B)
for (const auto &y : C)
{
vector <Node> D = x;
for (const auto &z : y) D.pb(z);
Node new_node;
new_node.opcode = 2;
new_node.son[0] = (int) y.size() + 1;
new_node.son[1] = 1;
D.pb(new_node);
vector <Node> E = x;
for (const auto &z : y) E.pb(z);
new_node.opcode = 3;
new_node.son[0] = (int) y.size() + 1;
new_node.son[1] = 1;
E.pb(new_node);
A.pb(D), A.pb(E);
}
}
return A;
}
if (state == 2)
{
vector <vector <Node> > A = generate_expr(deep, 3);
for (int lef = 0; lef <= deep - 2; lef++)
{
int rig = deep - 2 - lef;
{
vector <vector <Node> > B = generate_expr(lef, 0);
vector <vector <Node> > C = generate_expr(rig, 0);
for (const auto &x : B)
for (const auto &y : C)
{
vector <Node> D = x;
for (const auto &z : y) D.pb(z);
Node new_node;
new_node.opcode = 4;
new_node.son[0] = (int) y.size() + 1;
new_node.son[1] = 1;
D.pb(new_node);
vector <Node> E = x;
for (const auto &z : y) E.pb(z);
new_node.opcode = 5;
new_node.son[0] = (int) y.size() + 1;
new_node.son[1] = 1;
E.pb(new_node);
A.pb(D), A.pb(E);
}
}
}
return A;
}
if (state == 3)
{
if (deep == 0)
{
Node new_node;
new_node.opcode = 6;
return {{new_node}};
}
vector <vector <Node> > A = generate_expr(deep - 1, 0);
vector <vector <Node> > res;
for (const auto &x : A)
{
vector <Node> B = x, C = x;
Node new_node;
new_node.opcode = 0;
new_node.son[0] = 1;
B.pb(new_node);
new_node.opcode = 1;
new_node.son[0] = 1;
C.pb(new_node);
res.pb(B), res.pb(C);
}
return res;
}
return {};
}
string recover_answer(vector <Node> tree)
{
Node last = tree.back();
string ans;
if (last.opcode == 0)
{
string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - 1));
ans = "sin(" + L + ")";
}
if (last.opcode == 1)
{
string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - 1));
ans = "cos(" + L + ")";
}
if (last.opcode == 2)
{
int lef = last.son[0];
string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
ans = L + "+" + R;
}
if (last.opcode == 3)
{
int lef = last.son[0];
string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
ans = L + "-" + R;
}
if (last.opcode == 4)
{
int lef = last.son[0];
string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
ans = "(" + L + ")/(" + R + ")";
}
if (last.opcode == 5)
{
int lef = last.son[0];
string L = recover_answer(vector <Node>(tree.begin(), tree.begin() + (int) tree.size() - lef));
string R = recover_answer(vector <Node>(tree.begin() + (int) tree.size() - lef, tree.begin() + (int) tree.size() - 1));
ans = "(" + L + ")*(" + R + ")";
}
if (last.opcode == 6)
{
ans = "x";
}
return ans;
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> valx[i] >> valy[i];
vector <vector <Node> > all_var;
for (int i = 0; i <= 9; i++)
{
vector <vector <Node> > res = generate_expr(i, 0);
for (const auto &x : res) all_var.pb(x);
}
for (const auto &tree : all_var)
{
bool FLAG = true;
for (int num = 0; num < (int) tree.size(); num++)
{
const Node &node = tree[num];
if (node.opcode == 0)
{
int pr = num - node.son[0];
for (int i = 1; i <= n; i++) result[i][num] = sin(result[i][pr]);
}
if (node.opcode == 1)
{
int pr = num - node.son[0];
for (int i = 1; i <= n; i++) result[i][num] = cos(result[i][pr]);
}
if (node.opcode == 2)
{
int lef = num - node.son[0];
int rig = num - node.son[1];
for (int i = 1; i <= n; i++) result[i][num] = result[i][lef] + result[i][rig];
}
if (node.opcode == 3)
{
int lef = num - node.son[0];
int rig = num - node.son[1];
for (int i = 1; i <= n; i++) result[i][num] = result[i][lef] - result[i][rig];
}
if (node.opcode == 4)
{
int lef = num - node.son[0];
int rig = num - node.son[1];
for (int i = 1; i <= n; i++)
{
if (fabs(result[i][rig]) < EPS) {FLAG = false; continue;}
result[i][num] = result[i][lef] / result[i][rig];
}
}
if (node.opcode == 5)
{
int lef = num - node.son[0];
int rig = num - node.son[1];
for (int i = 1; i <= n; i++) result[i][num] = result[i][lef] * result[i][rig];
}
if (node.opcode == 6)
{
for (int i = 1; i <= n; i++) result[i][num] = valx[i];
}
}
//cout << recover_answer(tree) << '\n';
if (!FLAG) continue;
bool ANS = true;
for (int i = 1; i <= n; i++)
if (fabs(valy[i] - result[i][(int) tree.size() - 1]) > EPS_RES) ANS = false;
if (!ANS) continue;
string ans = recover_answer(tree);
cout << ans << '\n';
exit(0);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 106ms
memory: 159212kb
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: 93ms
memory: 158004kb
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: 103ms
memory: 158404kb
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: 99ms
memory: 159104kb
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: 99ms
memory: 157144kb
input:
5 78.611917 -0.992212 -29.857271 1.011993 -75.513655 1.006611 68.512394 1.145128 7.961096 0.881661
output:
cos(x)+(sin(x))*(sin(x))
result:
ok great!!
Test #6:
score: 0
Accepted
time: 101ms
memory: 159248kb
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))))
result:
ok great!!
Test #7:
score: 0
Accepted
time: 83ms
memory: 159656kb
input:
5 3.241091 -32.628130 -83.514144 86.463432 33.586619 40.691607 41.123543 -147.352644 26.896326 27.404018
output:
(x)/(sin(x))
result:
ok great!!
Test #8:
score: 0
Accepted
time: 479ms
memory: 159632kb
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:
sin(sin((x)/(sin((x)/((x)*(x))))))
result:
ok great!!
Test #9:
score: 0
Accepted
time: 234ms
memory: 157936kb
input:
20 76.797930 0.000002 -76.263778 -0.000002 55.449039 0.000006 10.462093 0.000873 -78.051671 -0.000002 -52.781249 -0.000007 47.053973 0.000010 96.629212 0.000001 -40.697847 -0.000015 31.141805 0.000033 -87.087384 -0.000002 -54.709885 -0.000006 -65.741847 -0.000004 -87.430820 -0.000001 9.420126 0.0011...
output:
(x)/((x)*((x)*((x)*(x))))
result:
ok great!!
Test #10:
score: 0
Accepted
time: 107ms
memory: 158728kb
input:
20 24.490647 23.891773 17.327799 16.329001 21.204241 21.912414 83.489542 84.461510 -55.546573 -54.703972 -7.608368 -8.578356 -3.286697 -3.142101 -66.606831 -66.014954 -44.896454 -45.688502 97.541741 97.389961 -59.986043 -59.694554 57.723989 58.646803 -99.857351 -99.233536 29.134673 28.376609 -98.668...
output:
x+sin(x)
result:
ok great!!
Test #11:
score: 0
Accepted
time: 82ms
memory: 159792kb
input:
20 89.594917 88.596688 -45.187625 -44.253669 97.451471 97.513530 35.078537 35.576300 82.504351 81.771201 -49.755211 -50.243625 -23.019693 -23.876242 -45.247155 -44.293590 75.324114 75.398156 78.533049 78.526282 99.112156 100.100628 31.983437 31.445903 71.251578 70.407388 -44.178279 -43.983549 -25.28...
output:
x-sin(x)
result:
ok great!!
Test #12:
score: 0
Accepted
time: 107ms
memory: 159664kb
input:
20 16.664144 7.850741 44.708237 22.196248 -10.852343 1.533223 -42.713221 -12.119419 -27.815914 -11.038511 31.908696 13.299065 -82.394044 40.761558 -37.317157 -12.907073 -35.369997 17.659068 93.569121 -45.722539 -30.589159 -15.242258 16.180069 6.553209 56.572831 1.366451 99.591187 -47.440823 12.73229...
output:
(x)*((sin(x))*(cos(x)))
result:
ok great!!
Test #13:
score: 0
Accepted
time: 86ms
memory: 160040kb
input:
20 -583.519562 0.000000 -169.653469 0.000000 372.798856 0.000000 180.084282 0.000000 139.388742 0.000000 -648.300263 0.000000 -859.523046 0.000000 -267.278551 0.000000 635.554372 0.000000 299.925737 0.000000 -628.299469 0.000000 169.393099 0.000000 556.144161 0.000000 -881.876627 0.000000 328.692044...
output:
x-x
result:
ok great!!
Test #14:
score: 0
Accepted
time: 84ms
memory: 159692kb
input:
20 746.491049 746.491049 414.031997 414.031997 -975.051138 -975.051138 45.313068 45.313068 -181.090458 -181.090458 119.607074 119.607074 245.794647 245.794647 -794.156219 -794.156219 461.647608 461.647608 -392.604379 -392.604379 384.522118 384.522118 -461.749513 -461.749513 766.462890 766.462890 244...
output:
x
result:
ok great!!
Test #15:
score: 0
Accepted
time: 110ms
memory: 157280kb
input:
20 4.278335 0.092599 3.559350 0.559919 -2.517239 0.403581 -0.955317 0.182475 3.048015 0.888213 -0.638367 0.393205 -2.188885 0.183959 -0.367275 0.597938 1.106453 0.948186 0.339096 0.971773 -0.678258 0.364003 4.364111 0.060002 -0.671364 0.369012 -2.777257 0.600136 1.617698 0.909755 -3.400784 0.950952 ...
output:
sin(sin(x)+(x)/(x))
result:
ok great!!
Test #16:
score: 0
Accepted
time: 1380ms
memory: 159392kb
input:
20 3.692126 -0.260752 0.663419 1.200876 1.167172 0.874743 4.852602 0.631308 3.373109 -0.334749 4.749943 0.529545 -2.549440 -0.245748 -1.158832 0.881804 4.115764 -0.040747 -3.401216 -0.330886 -4.320685 0.119451 -0.070540 1.332133 -4.666465 0.446117 -4.720184 0.499803 -1.731319 0.332854 4.232513 0.046...
output:
sin(cos(x))+sin(sin(cos((x)/(x))))
result:
ok great!!
Test #17:
score: 0
Accepted
time: 561ms
memory: 158636kb
input:
20 1.462467 0.804429 -2.922001 0.192241 4.580542 -0.620639 -0.475001 -0.799291 -1.988595 -0.234001 1.262913 0.840075 -3.176510 -0.034797 2.030387 0.180297 -3.244547 -0.099928 -3.321420 -0.164361 -0.538138 -0.818609 2.485817 -0.209990 -0.282936 -0.652106 0.964792 0.840607 -1.300754 -0.837872 4.323400...
output:
sin(sin(sin(x)+sin(sin(x+x))))
result:
ok great!!
Test #18:
score: 0
Accepted
time: 154ms
memory: 158472kb
input:
20 -1.290592 0.818752 0.639318 0.516086 -4.576452 0.791075 2.349231 0.829843 3.053369 0.646833 -4.276424 0.836563 -4.295090 0.835111 1.704429 0.790551 1.694925 0.788364 0.763954 0.527671 -0.477936 0.769603 0.395468 0.525360 0.686854 0.519231 -1.940048 0.637497 2.188388 0.840879 1.028990 0.584344 3.9...
output:
sin(cos(sin(x+cos(x-x))))
result:
ok great!!
Test #19:
score: -100
Wrong Answer
time: 112ms
memory: 160168kb
input:
20 -0.425664 0.425664 5.789130 -5.789130 -3.787451 3.787451 0.301151 -0.301151 -8.592688 8.592688 2.669073 -2.669073 5.308311 -5.308311 -0.139985 0.139985 -5.857648 5.857648 -4.992568 4.992568 6.105319 -6.105319 -3.765244 3.765244 5.912188 -5.912188 -6.224392 6.224392 -0.543340 0.543340 3.434037 -3....
output:
x-x+x
result:
wrong answer fail to discover