← 返回题目列表

Codeforces · 369/D

D. 瓦莱拉和傻瓜

中文机器翻译题面 查看原题

一个晴朗的早晨,n 个傻瓜排成一排。然后,他们用从1到n(含)的数字给彼此编号。每个傻瓜都有一个唯一的号码。傻瓜们决定在欢乐结束之前不改变他们的数字。

每个傻瓜都有恰好 k 颗子弹和一把手枪。此外,编号为 i 的傻瓜杀死他所射中的傻瓜的概率为 pi(百分比)。

傻瓜们决定玩几轮。每轮的乐趣都是这样的:每个当前活着的傻瓜向另一个数量最小的活着的傻瓜射击(傻瓜还没有愚蠢到向自己开枪)。这一轮的所有击球都是一次性(同时)进行的。如果正好有一个活着的傻瓜,他就不会开枪。

让我们将情况定义为某一时刻所有活着的傻瓜的数字集合。如果对于某个整数 j (0 ≤ j ≤ k),在 j 轮乐趣之后出现这种情况的概率非零,我们就说这种情况是可能的。

Valera 知道数字 p1、p2、...、pn 和 k。帮助瓦莱拉确定不同可能情况的数量。

输入

第一行包含两个整数n, k (1 ≤ n, k ≤ 3000)——初始的傻瓜数量和每个傻瓜的子弹数量。

第二行包含 n 个整数 p1, p2, ..., pn (0 ≤ pi ≤ 100) — 给定的概率(以百分比表示)。

输出

打印一个数字——问题的答案。

示例

输入 #1

3 3
50 50 50

输出 #1

7

输入 #2

1 1
100

输出 #2

1

输入 #3

2 1
100 100

输出 #3

2

输入#4

3 3
0 0 0

输出#4

1

注意

在第一个示例中,除了情况 {1, 2} 之外,任何情况都是可能的。

第二个样本中正好有一个傻瓜,所以他没有出手。

在第三个示例中,可能的情况是 {1, 2}(零轮后)和“空”情况 {}(一轮后)。

在第四个示例中,唯一可能的情况是 {1, 2, 3}。