TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

55.6% (5/9)

Tags

Description

閃躲了許久, 不但無法反擊, 體力也不斷地消耗.

楓音和妁艷明白了現在的狀況---根本就是魔王單方面虐殺.

魔王不但會召喚小怪, 會自己補血, 會吸魔力, 會暗闇系魔法, 還會超音波.
魔:好孩子,你可願跟我去?我的女兒也正在等你,每天晚上和你唱歌和遊戲,她唱歌和跳舞使你歡喜,她唱歌和跳舞使你歡喜。

在絕望之中, 楓音想出了最後的方法.

"這場戰鬥, 是命中注定了吧?"

"???"

"再這樣下去也不是辦法, ..., 妁艷君, 拿走我的力量吧..."

"楓音, 妳在說什麼...? 妳是說, 妳想要...? 別開玩笑了!"

"已經沒辦法了..., 再這樣下去我們都會..., 如果只是犧牲了我就能讓一切結束的話..."

"但是! 但是!......"

"妁艷君, 你最重要的妹妹還在等著你呢! 你一定要解救她... 你必須向前..., 別管我了..."

說到這邊, 兩人都淚流滿面了.

"雖然相處的時間很短, 但這段時間是我這生中過得最快樂的時光了. 謝謝你, 妁艷君!"

"不要啊! 楓音! 不要把我......"

話還沒說完, 楓音已經化為一道顆光球, 進入妁艷身體裡面了.

"......丟下......."

難過得快要崩潰了.

妁艷用兇狠的眼神看著魔王, 魔王則是一副很無辜的模樣.

"你這傢伙!!!"("鐵煤!!!")

妁艷衝向了魔王.

魔王的身體是由S個基本單位組成. 雖然每個基本單位都很脆弱, 但合在一塊就會變得十分強韌.

妁艷的武器已經賦有楓音靈魂的力量, 可以斬斷任何堅硬的東西, 包括魔王的身體.

妁艷可以花費的魔力將一塊大小為N的魔王身體斬成任意兩塊, 每個塊必須包含整數個基本單位.

當魔王的身體的S個基本單位全部都分開時, 魔王才算死亡.

妁艷至少要花費最少的魔力才能打敗魔王呢?

Input Format

第一行有兩個數字S, M (1 ≤ S ≤ M ≤ 2,147,483,647), 意義如上文所述.

Output Format

輸出唯一的數字, 代表妁艷至少要花費多少魔力才能打敗魔王.

Sample Input 1

4 16

Sample Output 1

17

Hints

花費最少魔力的過程如下:
{4} → {2, 2} → {1, 1, 2} → {1, 1, 1, 1}

第一次花費 + + = 4 + 3 + 2 = 9 的魔力.
第二, 三次花費 = 4的魔力.

故9 + 4 + 4 = 17.

據說這是魔王本體:

金屬史萊姆超難抓, 還要抓好幾隻來交配= ="

Problem Source

原TIOJ1772 / problem setter: willyliu; source: TAOCP 2.3.4.5-17

Subtasks

No. Testdata Range Score
1 0 2
2 1 2
3 2 2
4 3 2
5 4 2
6 5 2
7 6 2
8 7 2
9 8 2
10 9 2
11 10 2
12 11 2
13 12 2
14 13 2
15 14 2
16 15 2
17 16 2
18 17 2
19 18 2
20 19 2
21 20 2
22 21 2
23 22 2
24 23 2
25 24 2
26 25 2
27 26 2
28 27 2
29 28 2
30 29 2
31 30 2
32 31 2
33 32 2
34 33 2
35 34 2
36 35 2
37 36 2
38 37 2
39 38 2
40 39 2
41 40 2
42 41 2
43 42 2
44 43 2
45 44 2
46 45 2
47 46 2
48 47 2
49 48 2
50 49 2

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1
1 1500 65536 262144 2
2 1500 65536 262144 3
3 1500 65536 262144 4
4 1500 65536 262144 5
5 1500 65536 262144 6
6 1500 65536 262144 7
7 1500 65536 262144 8
8 1500 65536 262144 9
9 1500 65536 262144 10
10 1500 65536 262144 11
11 1500 65536 262144 12
12 1500 65536 262144 13
13 1500 65536 262144 14
14 1500 65536 262144 15
15 1500 65536 262144 16
16 1500 65536 262144 17
17 1500 65536 262144 18
18 1500 65536 262144 19
19 1500 65536 262144 20
20 1500 65536 262144 21
21 1500 65536 262144 22
22 1500 65536 262144 23
23 1500 65536 262144 24
24 1500 65536 262144 25
25 1500 65536 262144 26
26 1500 65536 262144 27
27 1500 65536 262144 28
28 1500 65536 262144 29
29 1500 65536 262144 30
30 1500 65536 262144 31
31 1500 65536 262144 32
32 1500 65536 262144 33
33 1500 65536 262144 34
34 1500 65536 262144 35
35 1500 65536 262144 36
36 1500 65536 262144 37
37 1500 65536 262144 38
38 1500 65536 262144 39
39 1500 65536 262144 40
40 1500 65536 262144 41
41 1500 65536 262144 42
42 1500 65536 262144 43
43 1500 65536 262144 44
44 1500 65536 262144 45
45 1500 65536 262144 46
46 1500 65536 262144 47
47 1500 65536 262144 48
48 1500 65536 262144 49
49 1500 65536 262144 50