TopCoder

Caido
Waimai

User's AC Ratio

40.0% (2/5)

Submission's AC Ratio

20.0% (7/35)

Tags

Description

Minecraft是一款沙盒遊戲,最初由瑞典遊戲設計師馬庫斯·阿列克謝·泊松單獨開發,隨後由2009年成立的瑞典公司Mojang開發並發行。玩家可以在一個隨機生成的3D世界內,以帶材質貼圖的立方體為基礎進行遊戲。 --維基百科

Minecraft中,有許多物品會放在背包中。背包由許多格子組成,每個格子都可以放無限個相同種類的東西(實際遊戲中其實只能放64個,不過我們在本題中忽略這個限制)

在某些情況下,你需要把某些物品拿起來放到別的地方。在遊戲中,「把東西拿起來」這個動作是由一系列的滑鼠動作完成的。
假設當前已經拿起了Q個東西,則在某個有L個相同東西的格子上按下滑鼠,會發生的事情如下:

  1. Q=0,且按的是左鍵,則會把L個東西全部拿起來,該格子被清空。
  2. Q=0,且按的是右鍵,則會把L2個東西拿起來,留下L2個東西。
  3. Q0,且按的是左鍵,則會把Q個東西全部放到該格子中,也就是該格子的東西會變成L+Q個。
  4. Q0,且按的是右鍵,則會把1個東西放到該格子中,也就是該格子的東西會變成L+1個,手上留下Q1個東西。

現在你的背包中有一個格子裝了N個鑽石(其它格子都是空的),並且你已經拿起了M個鑽石。請問如果你希望讓拿起的鑽石數量變成K,請問你至少需要點多少次滑鼠?

Input Format

輸入的第一行有一個正整數T,代表測資數量。
接下來T行,每行代表一筆測資,包含三個非負整數N,M,K,意義如題目所述。

對於所有測資,T30;KN+M200

子任務(測資)額外限制分數
1(0~3)M=0,N12527
2(4~7)N+M2013
3(4~11)N+M4017
4(4~15)N+M9020
5(0~19)N+M12523
6(0~23)N+M14025
7(0~27)N+M16025
8(0~31)N+M18025
9(0~35)無限制25

Output Format

請對每筆測資輸出一行,代表最少需要點幾次滑鼠。

Sample Input 1

3
17 0 7
19 13 12
8 6 9

Sample Output 1

3
1
3

Hints

每筆範例測資的按法如下:

第一筆:在有東西的那格連續按三次右鍵。
第二筆:按一次右鍵。
第三筆:在8個的格子按右鍵(該格變成9個)、在空的格子按左鍵、然後在9個的格子按左鍵。

TIOJ 第10000筆測資就在這題喔(?)

Problem Source

Problem Set / Description by Yihda Yol
建國中學106學年度校隊補選pC

Subtasks

No. Testdata Range Score
1 0~3 27
2 4~7 13
3 4~11 17
4 4~15 20
5 0~19 23
6 0~23 25
7 0~27 25
8 0~31 25
9 0~35 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 262144 32768 1 5 6 7 8 9
1 2500 262144 32768 1 5 6 7 8 9
2 2500 262144 32768 1 5 6 7 8 9
3 2500 262144 32768 1 5 6 7 8 9
4 2500 262144 32768 2 3 4 5 6 7 8 9
5 2500 262144 32768 2 3 4 5 6 7 8 9
6 2500 262144 32768 2 3 4 5 6 7 8 9
7 2500 262144 32768 2 3 4 5 6 7 8 9
8 2500 262144 32768 3 4 5 6 7 8 9
9 2500 262144 32768 3 4 5 6 7 8 9
10 2500 262144 32768 3 4 5 6 7 8 9
11 2500 262144 32768 3 4 5 6 7 8 9
12 2500 262144 32768 4 5 6 7 8 9
13 2500 262144 32768 4 5 6 7 8 9
14 2500 262144 32768 4 5 6 7 8 9
15 2500 262144 32768 4 5 6 7 8 9
16 2500 262144 32768 5 6 7 8 9
17 2500 262144 32768 5 6 7 8 9
18 2500 262144 32768 5 6 7 8 9
19 2500 262144 32768 5 6 7 8 9
20 2500 262144 32768 6 7 8 9
21 2500 262144 32768 6 7 8 9
22 2500 262144 32768 6 7 8 9
23 2500 262144 32768 6 7 8 9
24 2500 262144 32768 7 8 9
25 2500 262144 32768 7 8 9
26 2500 262144 32768 7 8 9
27 2500 262144 32768 7 8 9
28 2500 262144 32768 8 9
29 2500 262144 32768 8 9
30 2500 262144 32768 8 9
31 2500 262144 32768 8 9
32 2500 262144 32768 9
33 2500 262144 32768 9
34 2500 262144 32768 9
35 2500 262144 32768 9