c260: 吃蛋糕
標籤 :
通過比率 : 79% (11 人 / 14 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-09-10 22:15

內容 :

歪皮的生日到了,所以小彭買了一個長條形的蛋糕與歪皮一起享用。這個蛋糕非常的長,我們可以把它由左至右分為n個區塊,依序編號為1~n,每個區塊有一個美味程度ai(也有可能有非常難吃的區塊,美味程度是負的)。由於歪皮是壽星,他可以先切一段蛋糕下來享用,一段蛋糕的意思是一些相鄰的蛋糕區塊。為了滿足自己的口腹之慾,他決定自己切下來的這段蛋糕中每個區塊的美味程度的平均值要大於等於a;但他怕自己顯得太過貪婪,所以他決定切下來那段的美味程度平均值不能大於b。請問有幾種切法可以滿足他的要求?

例如:n=3,a=3,b=7,蛋糕每個區塊的美味程度依序為1,5,15,則(5),(1,5),(1,5,15)這3段是符合要求的,所以答案為3。

輸入說明

每筆測資的第一行有3個整數n,a,b;第二行有n個數字,依序為a1~an

(1≦n≦105,-109≦a≦b≦109,-109≦ai≦109)

輸出說明

對於每一筆測資請輸出一個數字代表有幾種切法。

範例輸入
//sample input 1
3 3 7
1 5 15
//sample input 2
2 -1 1
-5 5
範例輸出
//sample output 1
3
//sample output 2
1
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (20%): 1.0s , <1M
不公開 測資點#1 (20%): 1.0s , <1M
不公開 測資點#2 (20%): 1.0s , <1M
不公開 測資點#3 (20%): 1.0s , <1M
不公開 測資點#4 (20%): 1.0s , <1M
提示 :

輸出的數字有可能會很大!

測資配置:
(1)測資點1(20分):n≦1000
(2)測資點2(20分):第2個區塊至第n個區塊的美味程度都介於a與b之間
(3)測資點3(20分):每個區塊的美味程度都大於等於它左邊的區塊的美味程度
(4)測資點4(20分):1≦ai≦10
(5)測資點5(20分):沒有任何特殊限制

標籤:
出處:
陳威翰以及彭道耘 [編輯:
VacationClub (雄中公假社)
]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」