二次元傳送門

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

菌瑋非常的熱愛二次元,並且非常渴望進入二次元去找他的老婆:佩爾西亞。
在西元9487年的時候,他利用了油滴實驗測出了「油子」的質量,並且開發出了史上第一個二次元傳送門。
一開始他非常開心,但是過了不久之後就注意到了幾個重大的問題:

  1. 傳送門的啟動時間為一天,超過時間限制就會關閉,若要繼續進入二次元則需要再消耗「油子」以再次啟動。
  2. 每次啟動傳送門的時候,需要「油子」的數量也跟著增加(需要的數量至少為前一次啟動時油子的數量+\(x\),第一天啟動所需「油子」數量沒有限制)。
  3. 由於油子質量很小很難取特定的量,所以菌瑋只能拿手上「全部」的「油子」去啟動傳送門。

現在有\(n\)天,每天菌瑋持有的「油子」數量不一定會相同,且每天的油子會因為衰變成「油電子」以至於不能使用之前的「油子」。
菌瑋非常喜愛他的老婆,請問他最多可以啟動幾天的傳送門使得他能與佩爾西亞見面?

Input

第一行給定兩整數,分別代表\(n\)及\(x\)。
接下來第二行有\(n\)個正整數\(a_1, a_2, ..., a_n\),代表第\(i\)天持有的「油子」數量為多少。

Output

請輸出一個正整數,代表菌瑋最多可以啟動傳送門的天數。

Constraints

第 \(1\) 組測資, \(n\leq10\), \(x=1\)。 \((10\text{%})\)

第 \(2\) 組測資, \(n\leq10\)。 \((20\text{%})\)

第 \(3\) 組測資, \(n\leq10^2\), \(x=1\)。 \((15\text{%})\)

第 \(4\) 組測資, \(n\leq10^3\)。 \((20\text{%})\)

第 \(5\) 組測資, \(n\leq10^4\)。 \((35\text{%})\)

對於所有測資,\(1 \leq n,0 \leq x \leq 10^3, 1 \leq a_i \leq 10^6\)

Sample Input
7 3
8 1 5 6 4 7 1
Sample Output
3
(第2、5、6天啟動傳送門)

Comments

There are no comments at the moment.