TopCoder

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

User's AC Ratio

33.3% (1/3)

Submission's AC Ratio

9.5% (2/21)

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

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