40005. Practice 5: Minecraft

I'm a slow walker, but I never walk backwards.

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/Output

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

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

Subtasks/Constraints

所有測資皆符合: $T\leq 30; K\leq N+M\leq 140$

  1. $M=0$,$N+M\leq 125$ (24 pts)
  2. $N+M\leq 20$ (16 pts)
  3. $N+M\leq 40$ (16 pts)
  4. $N+M\leq 90$ (20 pts)
  5. $N+M\leq 125$ (20 pts)
  6. 無額外限制 (4 pts)

Sample Input

3
17 0 7
19 13 12
8 6 9

Sample Output

3
1
3

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

Discussion