QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372990#5271. Focusing on CostsFOY#RE 8ms4640kbC++231.6kb2024-03-31 22:25:022024-03-31 22:25:04

Judging History

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

  • [2024-03-31 22:25:04]
  • 评测
  • 测评结果:RE
  • 用时:8ms
  • 内存:4640kb
  • [2024-03-31 22:25:02]
  • 提交

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

output:


result: