QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372993 | #5271. Focusing on Costs | FOY# | TL | 1960ms | 87460kb | C++23 | 1.6kb | 2024-03-31 22:29:02 | 2024-03-31 22:29:04 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <numeric>
using namespace std;
using pii = pair<int, int>;
class Trans {
virtual string getName() = 0;
virtual pii act(pii cur) = 0;
};
int transCount = 6;
pii act(pii cur, int type) {
auto [a, b] = cur;
if (type == 0)
return {b - a, b};
if (type == 1)
return {a, b - a};
if (type == 2)
return {b - a, a};
if (type == 3)
return {b - a, b};
if (type == 4)
return {a, b + a};
if (type == 5)
return {b, a+b};
}
string getName(int type) {
if (type == 0) return "asin cos";
if (type == 1) return "asin tan";
if (type == 2) return "acos tan";
if (type == 3) return "acos sin";
if (type == 4) return "atan sin";
if (type == 5) return "atan cos";
}
int main() {
map<pii, pair<pii, int>> vis;
queue<pii> cur;
cur.push({0, 1});
int x, y; cin >> x >> y;
int a = x, b = y;
int u = gcd(a,b);
a/=u;
b/=u;
while (vis.count({a*a, b*b}) == 0) {
auto front = cur.front();
cur.pop();
if (abs(front.first) > 1e3 || abs(front.second) > 1e3) continue;
for (int t = 0; t < transCount; t++) {
auto to = act(front, t);
if (to.second <= 0) continue;
if (vis.count(to) == 0) {
vis[to] = {front, t};
cur.push(to);
}
}
}
pii end = {a*a, b*b};
vector<string> path;
while (end != make_pair(0, 1)) {
path.push_back(getName(vis[end].second));
end = vis[end].first;
}
cout << 2*path.size() << endl;
for (int i = path.size()-1; i >= 0; i--) cout << path[i]<< ' ';
cout <<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3820kb
input:
1 1
output:
2 asin cos
result:
ok OK, a/b = 1/1, ops = 2, error = 0.000000e+00
Test #2:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
2 1
output:
12 asin cos atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 2/1, ops = 12, error = 4.440892e-16
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 2
output:
8 asin cos atan sin atan sin atan sin
result:
ok OK, a/b = 1/2, ops = 8, error = 5.551115e-17
Test #4:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
1 3
output:
18 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 1/3, ops = 18, error = 5.551115e-17
Test #5:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
2 2
output:
2 asin cos
result:
ok OK, a/b = 2/2, ops = 2, error = 0.000000e+00
Test #6:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
3 1
output:
22 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 3/1, ops = 22, error = 0.000000e+00
Test #7:
score: 0
Accepted
time: 8ms
memory: 5324kb
input:
1 4
output:
32 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 1/4, ops = 32, error = 0.000000e+00
Test #8:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
2 3
output:
12 asin cos atan sin atan sin atan sin atan cos atan sin
result:
ok OK, a/b = 2/3, ops = 12, error = 0.000000e+00
Test #9:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
3 2
output:
16 asin cos atan sin atan sin atan sin atan cos atan sin atan sin acos tan
result:
ok OK, a/b = 3/2, ops = 16, error = 2.220446e-16
Test #10:
score: 0
Accepted
time: 61ms
memory: 9868kb
input:
4 1
output:
36 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 4/1, ops = 36, error = 1.776357e-15
Test #11:
score: 0
Accepted
time: 728ms
memory: 45708kb
input:
1 5
output:
50 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 1/5, ops = 50, error = 0.000000e+00
Test #12:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
2 4
output:
8 asin cos atan sin atan sin atan sin
result:
ok OK, a/b = 2/4, ops = 8, error = 5.551115e-17
Test #13:
score: 0
Accepted
time: 0ms
memory: 3480kb
input:
3 3
output:
2 asin cos
result:
ok OK, a/b = 3/3, ops = 2, error = 0.000000e+00
Test #14:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
4 2
output:
12 asin cos atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 4/2, ops = 12, error = 4.440892e-16
Test #15:
score: 0
Accepted
time: 1043ms
memory: 53080kb
input:
5 1
output:
54 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 5/1, ops = 54, error = 8.881784e-16
Test #16:
score: 0
Accepted
time: 1540ms
memory: 70860kb
input:
1 6
output:
72 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin ...
result:
ok OK, a/b = 1/6, ops = 72, error = 2.775558e-17
Test #17:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
2 5
output:
20 asin cos atan sin atan sin atan sin atan cos atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 2/5, ops = 20, error = 5.551115e-17
Test #18:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
3 4
output:
14 asin cos atan sin atan cos atan sin atan sin atan cos atan cos
result:
ok OK, a/b = 3/4, ops = 14, error = 0.000000e+00
Test #19:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
4 3
output:
18 asin cos atan sin atan cos atan sin atan sin atan cos atan cos atan sin acos tan
result:
ok OK, a/b = 4/3, ops = 18, error = 2.220446e-16
Test #20:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
5 2
output:
24 asin cos atan sin atan sin atan sin atan cos atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 5/2, ops = 24, error = 8.881784e-16
Test #21:
score: 0
Accepted
time: 1558ms
memory: 72924kb
input:
6 1
output:
76 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin ...
result:
ok OK, a/b = 6/1, ops = 76, error = 3.552714e-15
Test #22:
score: 0
Accepted
time: 1752ms
memory: 80372kb
input:
1 7
output:
98 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin ...
result:
ok OK, a/b = 1/7, ops = 98, error = 2.775558e-17
Test #23:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 6
output:
18 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 2/6, ops = 18, error = 5.551115e-17
Test #24:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
3 5
output:
16 asin cos atan sin atan cos atan sin atan sin atan cos atan cos atan sin
result:
ok OK, a/b = 3/5, ops = 16, error = 0.000000e+00
Test #25:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
4 4
output:
2 asin cos
result:
ok OK, a/b = 4/4, ops = 2, error = 0.000000e+00
Test #26:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
5 3
output:
20 asin cos atan sin atan cos atan sin atan sin atan cos atan cos atan sin atan sin acos tan
result:
ok OK, a/b = 5/3, ops = 20, error = 0.000000e+00
Test #27:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
6 2
output:
22 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 6/2, ops = 22, error = 0.000000e+00
Test #28:
score: 0
Accepted
time: 1886ms
memory: 81120kb
input:
7 1
output:
102 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin...
result:
ok OK, a/b = 7/1, ops = 102, error = 3.552714e-15
Test #29:
score: 0
Accepted
time: 1957ms
memory: 84568kb
input:
1 8
output:
128 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin...
result:
ok OK, a/b = 1/8, ops = 128, error = 0.000000e+00
Test #30:
score: 0
Accepted
time: 14ms
memory: 5340kb
input:
2 7
output:
32 asin cos atan sin atan sin atan sin atan cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 2/7, ops = 32, error = 0.000000e+00
Test #31:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 6
output:
8 asin cos atan sin atan sin atan sin
result:
ok OK, a/b = 3/6, ops = 8, error = 5.551115e-17
Test #32:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 5
output:
16 asin cos atan sin atan cos atan sin atan sin atan cos atan cos atan cos
result:
ok OK, a/b = 4/5, ops = 16, error = 0.000000e+00
Test #33:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
5 4
output:
20 asin cos atan sin atan cos atan sin atan sin atan cos atan cos atan cos atan sin acos tan
result:
ok OK, a/b = 5/4, ops = 20, error = 0.000000e+00
Test #34:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
6 3
output:
12 asin cos atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 6/3, ops = 12, error = 4.440892e-16
Test #35:
score: 0
Accepted
time: 66ms
memory: 10396kb
input:
7 2
output:
36 asin cos atan sin atan sin atan sin atan cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 7/2, ops = 36, error = 8.881784e-16
Test #36:
score: 0
Accepted
time: 1843ms
memory: 84980kb
input:
8 1
output:
132 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin...
result:
ok OK, a/b = 8/1, ops = 132, error = 6.217249e-15
Test #37:
score: 0
Accepted
time: 1847ms
memory: 87280kb
input:
1 9
output:
162 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin...
result:
ok OK, a/b = 1/9, ops = 162, error = 0.000000e+00
Test #38:
score: 0
Accepted
time: 8ms
memory: 5104kb
input:
2 8
output:
32 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 2/8, ops = 32, error = 0.000000e+00
Test #39:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 7
output:
22 asin cos atan sin atan sin atan sin atan cos atan sin atan cos atan sin atan sin atan sin atan sin
result:
ok OK, a/b = 3/7, ops = 22, error = 0.000000e+00
Test #40:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
4 6
output:
12 asin cos atan sin atan sin atan sin atan cos atan sin
result:
ok OK, a/b = 4/6, ops = 12, error = 0.000000e+00
Test #41:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 5
output:
2 asin cos
result:
ok OK, a/b = 5/5, ops = 2, error = 0.000000e+00
Test #42:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
6 4
output:
16 asin cos atan sin atan sin atan sin atan cos atan sin atan sin acos tan
result:
ok OK, a/b = 6/4, ops = 16, error = 2.220446e-16
Test #43:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
7 3
output:
26 asin cos atan sin atan sin atan sin atan cos atan sin atan cos atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 7/3, ops = 26, error = 4.440892e-16
Test #44:
score: 0
Accepted
time: 55ms
memory: 9628kb
input:
8 2
output:
36 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin acos tan
result:
ok OK, a/b = 8/2, ops = 36, error = 1.776357e-15
Test #45:
score: 0
Accepted
time: 1960ms
memory: 87460kb
input:
9 1
output:
166 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin...
result:
ok OK, a/b = 9/1, ops = 166, error = 5.329071e-15
Test #46:
score: -100
Time Limit Exceeded
input:
1 10
output:
200 asin cos atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin atan sin...