QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#135596 | #6395. Equation Discovering | UrgantTeam# | WA | 1086ms | 93896kb | C++23 | 8.0kb | 2023-08-05 19:06:56 | 2023-08-05 19:06:57 |
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.01;
const ld EPS_RES = 0.001;
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, 1);
vector <vector <Node> > C = generate_expr(rig, 2);
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, 2);
vector <vector <Node> > C = generate_expr(rig, 3);
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);
}
}
if (rig >= 2)
{
vector <vector <Node> > B = generate_expr(lef, 2);
vector <vector <Node> > C = generate_expr(rig, 4);
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;
}
if (state == 4)
{
vector <vector <Node> > A;
for (int lef = 0; lef <= deep - 2; lef++)
{
int rig = deep - 2 - lef;
vector <vector <Node> > B = generate_expr(lef, 1);
vector <vector <Node> > C = generate_expr(rig, 2);
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;
}
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() - lef + 1, 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() - lef + 1, 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() - lef + 1, 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() - lef + 1, 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];
}
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 61ms
memory: 91896kb
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: 65ms
memory: 93896kb
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: 72ms
memory: 92300kb
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: 63ms
memory: 93816kb
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: 68ms
memory: 93492kb
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: 53ms
memory: 92448kb
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: 61ms
memory: 91784kb
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: 350ms
memory: 92708kb
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: 212ms
memory: 93132kb
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: 62ms
memory: 93144kb
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: 57ms
memory: 92432kb
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: 67ms
memory: 91864kb
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: 68ms
memory: 93384kb
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: 59ms
memory: 92428kb
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: 53ms
memory: 91580kb
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: 935ms
memory: 91652kb
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: 406ms
memory: 91928kb
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: 120ms
memory: 92376kb
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: 0
Accepted
time: 46ms
memory: 91516kb
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:
ok great!!
Test #20:
score: 0
Accepted
time: 64ms
memory: 92248kb
input:
20 466.316736 -0.978078 -899.828376 0.971830 493.698428 0.451443 543.034476 -0.444891 547.435563 -0.716269 -477.216617 -0.300738 397.144177 -0.964489 -215.994986 0.699650 -125.191685 -0.454687 -278.649888 0.814495 958.350526 0.164022 -505.445050 0.344182 -930.587439 0.625688 397.543136 -0.991345 -25...
output:
sin(x-x-x)
result:
ok great!!
Test #21:
score: 0
Accepted
time: 79ms
memory: 92676kb
input:
20 999.999999 0.987127 -999.999999 0.987127 100.000001 -0.333949 -100.000001 -0.333949 999.999998 -0.829877 -999.999998 -0.829877 512.000001 -0.871928 -512.000001 -0.871928 511.999999 -0.985382 -511.999999 -0.985382 0.000000 0.000000 0.000001 0.000000 -0.000001 0.000000 0.180000 0.001050 -0.180000 0...
output:
sin(x*(x)*(x)*(x))
result:
ok great!!
Test #22:
score: -100
Wrong Answer
time: 1086ms
memory: 93536kb
input:
20 0.009999 0.914653 0.009999 0.914653 0.009999 0.914653 0.009999 0.914653 0.009999 0.914653 0.009999 0.914653 0.009999 0.914653 1.000000 0.914653 1.000000 0.914653 2.005000 0.914653 2.005000 0.914653 3.000000 0.914653 3.000000 0.914653 0.009999 0.914653 0.009999 0.914653 0.009999 0.914653 0.009999 ...
output:
result:
wrong output format Unexpected end of file - token expected