2907 - 植物大战僵尸

题目描述

戴夫又要守护它的后花园了,据僵尸电视台尸潮预警今天晚上 0 点到 6 点间,会有 n 只僵尸妄图吃掉戴夫的脑子,下面会用 0 \sim 360 表示僵尸会在第几分钟来袭。

他已经预知了每只僵尸来袭的时间。这些僵尸害怕太阳花,如果场上同时存在 k 朵太阳花,就能把僵尸吓跑,也就是说如果僵尸出现时场上的太阳花不足 k 朵,那么戴夫的脑子就会被直接吃掉。每朵太阳花可以在场上停留 t 分钟,每个时刻只能种一朵太阳花

戴夫想知道,最少需要种下多少朵太阳花才能平安保住他的脑子?

输入

第一行包含 3 个整数 n、t、k

第二行 n 个整数,表示每只僵尸来的时间,时间单调递增

输出

输出最少需要太阳花的数量,如果不能把所有的僵尸赶跑,输出 The Zombies Ate Your Brains!

样例

输入

1 8 3
10

输出

3

输入

2 10 1
5 8

输出

1

输入

1 1 3
10

输出

The Zombies Ate Your Brains!
说明

说明

如果在第 x 时刻种一朵太阳花,那么这朵太阳花,会在[x+1,x+t] 这段时间停留在场上。

可以在任何时刻种下太阳花,但每个时刻只能种一朵,种花的时间为负数时,表示在午夜前。

样例 1 解释

1 只僵尸,太阳花可以在场上停留 8 分钟,只要场上有 3 朵太阳花,就能吓跑僵尸。

僵尸在第 10 分钟来袭。

最早可以在第 2 3 4 分钟分别种下一朵太阳花,当僵尸第 10 分钟来袭,场上有 3 朵太阳花。

最晚可以在第 7 8 9 分钟分别种下一朵太阳花,当僵尸第 10 分钟来袭,场上也有 3 朵太阳花。

当然在第 [2,9] 分钟的时间范围内,任意选 3 个时间点各种下一朵太阳花,都可以保证僵尸第 10 分钟来袭时,场上有 3 朵太阳花。

数据范围

对于 100\% 的数据, n、k、t 的范围 [1,300] ,僵尸来的时间 [0,360]

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


上一题 下一题