戴夫又要守护它的后花园了,据僵尸电视台尸潮预警今天晚上 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 只僵尸,太阳花可以在场上停留 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]。