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

範例輸出 #1

測資資訊：

記憶體限制： 512 MB

提示：

對於範例測資:

第一筆中，雖然背包重量限制很大，但只有1包糖果，所以小瀾只能獲得1顆糖果

第二筆中，小瀾可以將全部糖果裝進背包中，共獲得1+2=3顆糖果

第三筆中，小瀾可以獲得1+2=3顆糖果，重量花費為1^2+2^2=5<=7

第四筆中，小瀾可以獲得1+3=4顆糖果，重量花費為1^2+3^2=10<=10

標籤:

出處:

[管理者：

linlincaleb@ ... (臨末之頌) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」