QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372990 | #5271. Focusing on Costs | FOY# | RE | 8ms | 4640kb | C++23 | 1.6kb | 2024-03-31 22:25:02 | 2024-03-31 22:25:04 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
#include <map>
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 a, b; cin >> a >> b;
for (int i = 1; i <= min(a,b); i++) {
if (a%i == 0 && b%i == 0) {
a/=i;
b/=i;
}
}
while (vis.count({a*a, b*b}) == 0) {
auto front = cur.front();
cur.pop();
if (front.first*front.first > 1e4 || front.second*front.second > 1e4) 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: 3572kb
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: 3820kb
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: 3768kb
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: 1ms
memory: 3540kb
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: 3596kb
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: 3820kb
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: 2ms
memory: 3988kb
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: 1ms
memory: 3820kb
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: 3812kb
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: 5ms
memory: 4316kb
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: 7ms
memory: 4280kb
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: 3752kb
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: 1ms
memory: 3616kb
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: 3528kb
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: 7ms
memory: 4348kb
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: 2ms
memory: 4640kb
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: 3592kb
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: 3532kb
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: 3612kb
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: 3860kb
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: 7ms
memory: 4348kb
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: 8ms
memory: 4432kb
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: 1ms
memory: 3544kb
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: 3576kb
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: -100
Runtime Error
input:
4 4