TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

25.0% (1/4)

Submission's AC Ratio

16.7% (4/24)

Description

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

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

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

  1. 若$Q=0$,且按的是左鍵,則會把$L$個東西全部拿起來,該格子被清空。
  2. 若$Q=0$,且按的是右鍵,則會把$\lceil\frac{L}{2}\rceil$個東西拿起來,留下$\lfloor\frac{L}{2}\rfloor$個東西。
  3. 若$Q\neq 0$,且按的是左鍵,則會把$Q$個東西全部放到該格子中,也就是該格子的東西會變成$L+Q$個。
  4. 若$Q\neq 0$,且按的是右鍵,則會把1個東西放到該格子中,也就是該格子的東西會變成$L+1$個,手上留下$Q-1$個東西。

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

Input Format

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

對於所有測資,$T\leq 30; K\leq N+M\leq 200$。

子任務(測資)額外限制分數
1(0~3)$M=0,N\leq 125$27
2(4~7)$N+M\leq 20$13
3(4~11)$N+M\leq 40$17
4(4~15)$N+ M \leq 90$20
5(0~19)$N+M \leq 125$23
6(0~23)$N+M \leq 140$25
7(0~27)$N+M \leq 160$25
8(0~31)$N+M \leq 180$25
9(0~35)無限制25

Output Format

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

Sample Input

3
17 0 7
19 13 12
8 6 9

Sample Output

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