h935.
小瀾的背包(backpack)
內容
今天，壞壞的小瀾又來跟臨末要糖果吃囉，臨末本來想要敷衍小瀾一下，給他1顆糖果就完事了，可是，貪心的小瀾並不滿足，她還想要更多，所以臨末決定，讓小瀾自己裝糖果進她的背包，這些糖果都是一包一包的，每次只能以包為單位放入袋子裡。總共有N包糖果，裡面分別有1~N顆，這N包糖果中，含有X顆糖果的那包糖果，重量為X^2單位。小瀾的背包大小有限，於是請你幫她放糖果，請你告訴她最多可以獲得多少糖果呢?
配分：
subtask 1: 10% N<=2
subtask 2: 10% K<=2
subtask 3: 30% 1<=N<=400，1<=K<=400
subtask 4: 20% N=10^9
subtask 5: 30% 無額外限制
輸入說明
第一行有1個正整數T，代表有T筆測資(1<=T<=200000)
接下來T行，每行包含2個正整數N、K。代表有N包糖果可以選擇，小瀾的背包重量限制是K(1<=N<=10^9，1<=K<=10^9)
輸出說明
請輸出小瀾最多可以獲得幾顆糖果。
每次輸出後換行。
範例輸入
#1
4 1 1000000 2 5 3 7 3 10
範例輸出
#1
1 3 3 4
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (10%): 1.0s , <10M
公開 測資點#1 (10%): 1.0s , <10M
公開 測資點#2 (10%): 1.0s , <10M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <10M
公開 測資點#1 (10%): 1.0s , <10M
公開 測資點#2 (10%): 1.0s , <10M
公開 測資點#3 (10%): 1.0s , <10M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
對於範例測資:
第一筆中，雖然背包重量限制很大，但只有1包糖果，所以小瀾只能獲得1顆糖果
第二筆中，小瀾可以將全部糖果裝進背包中，共獲得1+2=3顆糖果
第三筆中，小瀾可以獲得1+2=3顆糖果，重量花費為1^2+2^2=5<=7
第四筆中，小瀾可以獲得1+3=4顆糖果，重量花費為1^2+3^2=10<=10
標籤:
出處:
[管理者：
linlincaleb@
...
(臨末之頌)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||