2024 . 背包問題
TopCoder
Description
Minecraft是一款沙盒遊戲，最初由瑞典遊戲設計師馬庫斯·阿列克謝·泊松單獨開發，隨後由2009年成立的瑞典公司Mojang開發並發行。玩家可以在一個隨機生成的3D世界內，以帶材質貼圖的立方體為基礎進行遊戲。 －－維基百科
Minecraft中，有許多物品會放在背包中。背包由許多格子組成，每個格子都可以放無限個相同種類的東西（實際遊戲中其實只能放64個，不過我們在本題中忽略這個限制）。
在某些情況下，你需要把某些物品拿起來放到別的地方。在遊戲中，「把東西拿起來」這個動作是由一系列的滑鼠動作完成的。
假設當前已經拿起了$Q$個東西，則在某個有$L$個相同東西的格子上按下滑鼠，會發生的事情如下：
- 若$Q=0$，且按的是左鍵，則會把$L$個東西全部拿起來，該格子被清空。
- 若$Q=0$，且按的是右鍵，則會把$\lceil\frac{L}{2}\rceil$個東西拿起來，留下$\lfloor\frac{L}{2}\rfloor$個東西。
- 若$Q\neq 0$，且按的是左鍵，則會把$Q$個東西全部放到該格子中，也就是該格子的東西會變成$L+Q$個。
- 若$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 1
3
17 0 7
19 13 12
8 6 9
17 0 7
19 13 12
8 6 9
Sample Output 1
3
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 |