QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372993#5271. Focusing on CostsFOY#TL 1960ms87460kbC++231.6kb2024-03-31 22:29:022024-03-31 22:29:04

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 22:29:04]
  • 评测
  • 测评结果:TL
  • 用时:1960ms
  • 内存:87460kb
  • [2024-03-31 22:29:02]
  • 提交

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...

result: