h935: 小瀾的背包(backpack)
Tags :
Accepted rate : 4人/6人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-09-10 18:37

Content

今天,壞壞的小瀾又來跟臨末要糖果吃囉,臨末本來想要敷衍小瀾一下,給他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% 無額外限制

Input

第一行有1個正整數T,代表有T筆測資(1<=T<=200000)

接下來T行,每行包含2個正整數N、K。代表有N包糖果可以選擇,小瀾的背包重量限制是K(1<=N<=10^9,1<=K<=10^9)

Output

請輸出小瀾最多可以獲得幾顆糖果。

每次輸出後換行。

Sample Input #1
4
1 1000000
2 5
3 7
3 10
Sample Output #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
Hint :

對於範例測資:

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

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

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

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

Tags:
出處:
[管理者: linlincaleb@...(臨末之頌) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」