4276 - 打水漂

题目描述

小 K 在湖边学打水漂。他把一块扁石子掷向平静的湖面,石子会贴着水面连续弹跳,总共触水 N+1 次。

以石子第一次触水的位置为基准点(记作离基准点 0 米),石子每次弹起后都会向前方飞出一段距离:第 i 次触水(2 \le i \le N+1)的位置比第 i-1 次远 L_{i-1} 米。

湖面上离基准点 X 米处漂着一个浮标。小 K 想知道:石子在浮标之前(即触水位置离基准点不超过 X 米)总共触水了多少次?

输入

输入共两行:

第一行两个整数 NX

第二行 N 个整数 L_1, L_2, \ldots, L_N,表示每次弹跳向前飞出的距离。

输出

一行,一个整数,表示触水位置不超过 X 米的触水次数。

样例

输入

3 8
2 5 4

输出

3

输入

6 20
4 3 6 2 5 7

输出

6

输入

12 45
5 8 2 9 4 7 1 6 3 10 2 8

输出

10
说明

样例说明

样例 1:石子依次在 0, 2, 7, 11 米处触水,其中 0, 2, 7 三处不超过 8 米,答案为 3。注意第一次触水在 0 米处,一定会被计入。

样例 2:石子依次在 0, 4, 7, 13, 15, 20, 27 米处触水,不超过 20 米的共 6 次。

样例 3:石子依次在 0, 5, 13, 15, 24, 28, 35, 36, 42, 45, 55, 57, 65 米处触水,不超过 45 米的共 10 次。特别注意:第 10 次触水的位置恰好45 米,"不超过"包含相等的情况,也要计入;把判断条件写成严格小于的程序会在这组数据上少算一次。

数据范围与提示

对于 100\% 的数据,1 \le N \le 1001 \le L_i \le 1001 \le X \le 10^4,输入均为整数。

本题共 20 个测试点,每个测试点 5 分。具体数据范围如下:

测试点编号N \leX \le特殊性质
1 \sim 1410010^4
1510010^4C
1611B、C
171010A
181010C
192010^2B
2010010^4A、B

特殊性质 A:所有 L_i 都相同。

特殊性质 B:所有 N+1 次触水的位置都不超过 X

特殊性质 C:只有第一次触水的位置不超过 X,答案为 1

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题