UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204199#3597. 最优操作smallstone100769ms8744kbC++11752b2024-05-02 11:08:542024-05-02 12:05:40

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
//using LL = __int128
ll c = 2e18, sz = 1e12, lim = 1e5, mv = 1e6;
ll use;
unordered_map<ll, int> mp, mp2;
void div(ll &t){
	while(!(t & 1))
		t /= 2;
}
ll check(ll x, int pre = 0){
	div(x);
	if(x <= 1ll)
		return x + pre;
	if(x <= 1000000){
		if(mp[x])
			return mp[x];
		return mp[x] = min(check((x + 1) >> 1) + 1, check(x >> 1) + 1);
	}
	if(x & 2ll)
		return check(x + 1) + 1;
	if((x & 4ll) && (x & 8ll))
		return check(x + 1) + 1;
	if(x & 4ll)
		return check(x - 1) + 1;
	return check(x - 1) + 1;
}
int main(){
	ll t;
	scanf("%lld", &t);
	while(t--){
		ll x;
		scanf("%lld", &x);
		printf("%lld\n", check(((x < 0) ? (-x) : x)));
	}
	return 0;
}
源文件, 语言: C++11

详细

小提示：点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1244kb

input:

10
-1
-2
3
4
-5
-6
7
-8
9
-10

output:

1
1
2
1
2
2
2
1
2
2

result:

ok 10 lines

Test #2:

score: 10
Accepted
time: 0ms
memory: 1248kb

input:

100
1
-2
3
4
-5
-6
-7
8
9
-10
-11
-12
-13
-14
-15
-16
17
18
19
-20
-21
-22
-23
24
-25
26
-27
-28
-29...

output:

1
1
2
1
2
2
2
1
2
2
3
2
3
2
2
1
2
2
3
2
3
3
3
2
3
3
3
2
3
2
2
1
2
2
3
2
3
3
3
2
3
3
4
3
4
3
3
2
3
3
...

result:

ok 100 lines

Test #3:

score: 10
Accepted
time: 0ms
memory: 1268kb

input:

1000
1
2
3
4
5
6
7
8
9
10
-11
-12
-13
-14
15
-16
-17
-18
19
20
-21
-22
-23
-24
-25
26
-27
-28
-29
-3...

output:

1
1
2
1
2
2
2
1
2
2
3
2
3
2
2
1
2
2
3
2
3
3
3
2
3
3
3
2
3
2
2
1
2
2
3
2
3
3
3
2
3
3
4
3
4
3
3
2
3
3
...

result:

ok 1000 lines

Test #4:

score: 10
Accepted
time: 76ms
memory: 8212kb

input:

100000
-231121
256906
613966
-224172
-333071
994969
151676
-388903
-487113
-944757
-889035
770700
-6...

output:

7
6
8
7
7
9
5
7
7
10
9
7
8
5
9
8
7
8
7
9
6
10
8
9
5
10
5
8
8
5
9
6
8
7
8
6
8
8
6
7
7
5
7
7
9
10
8
9
...

result:

ok 100000 lines

Test #5:

score: 10
Accepted
time: 60ms
memory: 8212kb

input:

100000
-908667
-562456
181546
-554932
-739170
-538954
720309
-38110
866233
608310
-54982
-786589
-35...

output:

7
7
8
6
8
7
8
6
8
7
7
6
8
7
9
7
8
7
7
7
8
8
7
7
6
9
7
8
8
8
7
8
8
7
8
7
7
8
7
9
5
6
5
8
7
7
9
4
8
9
...

result:

ok 100000 lines

Test #6:

score: 10
Accepted
time: 58ms
memory: 8216kb

input:

100000
-792937
-162616
-84421
-488532
-196589
-348075
-749731
186091
-578056
-173526
-55094
443712
-...

output:

9
6
7
7
5
8
8
8
6
8
7
6
8
7
8
7
7
6
7
5
8
8
7
8
6
6
10
7
7
5
8
8
9
7
8
7
7
7
6
7
7
8
5
6
6
8
7
10
7
...

result:

ok 100000 lines

Test #7:

score: 10
Accepted
time: 108ms
memory: 8740kb

input:

100000
253607128917732420
24408063907307269
117620878244041236
983765135055422340
268651110948098510...

output:

18
19
18
22
22
23
18
23
23
19
19
22
20
21
23
18
23
22
25
23
17
22
17
20
20
19
19
22
18
23
23
18
20
1...

result:

ok 100000 lines

Test #8:

score: 10
Accepted
time: 107ms
memory: 8744kb

input:

100000
-696377935053170490
-355212970239445107
-333306238170910973
-255251865730333904
-921799149072...

output:

21
17
17
21
25
19
22
19
21
19
22
21
20
22
20
19
20
20
19
22
20
18
23
19
23
20
25
20
22
23
17
19
19
1...

result:

ok 100000 lines

Test #9:

score: 10
Accepted
time: 173ms
memory: 8744kb

input:

100000
659146397167005125
546033109942061855
-27368974576746931
516768681479505510
26034241164991632...

output:

20
22
15
22
22
16
21
19
19
22
22
19
22
19
18
19
21
20
21
20
22
20
21
21
22
19
15
22
19
21
22
20
22
2...

result:

ok 100000 lines

Test #10:

score: 10
Accepted
time: 187ms
memory: 8740kb

input:

100000
917158593516630072
29757163513465913
-374400344927148529
-931396642079379928
8191114028391058...

output:

22
18
23
18
23
18
18
21
21
17
19
22
19
19
19
21
23
20
21
16
22
21
15
19
20
18
20
22
23
21
18
22
22
2...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed

中文 English

Server time: 2025-03-04 05:42:47 | 开源项目