回分類題庫
h058: B.電腦出租公司
關鍵字: NPSC 2009 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 21 Times / 14 Users | Submit : 57 Times / 17 Users | Accepted rate : 82%
題目加入時間 : 2012-11-04 02:07

Content: 简体中文

A 公司是一個電腦伺服器出租公司,現在總共有 N 台伺服器編號從 1 到 N,每一台伺服器都用一個正整數表示他的效能。當然一台伺服器通常不夠用,所以客人常常需要一次租很多台,多台伺服器的效能等於個別效能相加的總和。為了方便整理及運送,A 公司規定同一次出租的伺服器編號一定要連續。

A 公司對出租的定價,是根據他們所能提供的所有伺服器組合,效能總和由最高排到最低,最低的要 1 元,最好的要 (N+1)*N/2 元。舉例來說假設總共有三台伺服器效能分別是 1, 2, 4,則所有的效能組合由高排到低是 7, 6, 4, 3, 2, 1,而價錢分別是 6, 5, 4, 3, 2, 1。

現在有一個人想要租伺服器,他想要知道以他現有的錢可以租到效能多好的的伺服器組合。

Input:

第一行有一個整數代表總共有幾筆測試資料。每一筆測試資料有兩行。
第一行有 N, M 兩個整數,N 代表總共有幾台伺服器,M 代表你現在有多少錢。第二行有 N 個整數 A1 到 AN,分別代表第 1 台到第 N 台伺服器的效能。
0 < N < 1000000
0 < M <= (N+1)*N/2
0<= AN <= 10000

Output:

M 元可以租到的效能組合是多少 mod 1000000007

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 4
1 2 3
3 2
1 2 3

Sample Output :

3
2

Hint :

Author :

NPSC 2009 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum