qq820186690与achen的罪恶の手

qq820186690与achen的罪恶の手

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

qq820186690很喜欢玩游戏,无论在家里,在寝室,在机房,在厕所。
achen有很多罪恶の手,呃......塑料手,具体我们题目描述中说。

描述

qq820186690和achen住在同一个寝室,他们是很好的朋友和室友,算上他们俩寝室一共住了K个同学。
有一天,qq820186690突然意识到了玩游戏的危害,因此他于2012-9-3在发了一篇微博:

这很奇怪啊,qq820186690如果被发现玩游戏或者干一些与学习无关的事就会将一些“手”切成碎片。这个逻辑真是厉害了,不是吗?
我们将这些与qq820186690学习无关的事称作“坏事”。现在我们知道qq820186690如果在寝室待上T分钟就会开始做“坏事”,他会停止做这些“坏事”当他被achen警告或者他离开寝室。请注意,如果qq820186690被achen警告后又在宿舍待上T分钟,他又会重新干“坏事”。
achen注意到了qq820186690发布的这篇奇怪的微博,但是他是一个非常给力的室友,所以他决定冒着失去自己“手”的危险去警告qq820186690。辛运的是,achen有M只塑料玩具手,所以当qq820186690被警告时,他只会将这些玩具手切成碎片。
那么问题来了。作为生活老师的你只知道初始时没有人在寝室,并且我们听到了N声门开关的声音。我们准确地记录了这N次门开关的声音的发出时间,但是我们并不知道谁造成了这些声音,这意味着有N人/次进入或离开了寝室,任何K个住在寝室的同学有相同的概率进入/离开。
我们想要知道24小时(1440分钟)后可怜的achen期望剩下的塑料手的个数。
请注意achen使用塑料手去阻止qq820186690做“坏事”并不花费时间。这意味着一旦achen进入寝室,一只塑料手将会立即用于阻止qq820186690做“坏事”。但是如果没有塑料手剩余,achen便无法阻止qq820186690做“坏事”了。

格式

输入格式

第一行包含4个整数T(1≤T≤100),N(1≤N≤100),M(1≤M≤100)和K(2≤K≤8),它们的意义已经被描述。
第二行包含N个整数ti(0≤ti≤1440,0≤i<N),表示在时刻ti有一个学生进入或离开了寝室。
数据保证这N个时刻由严格递增顺序给出。

输出格式

输出在时刻1440,achen期望拥有的塑料手个数,保留到6位小数。

样例1

样例输入1

60 2 10 2 
200 260 

样例输出1

5.000000 

样例2

样例输入2

100 2 8 5 
1340 1341

样例输出2

7.960000

限制

每个测试点1s

提示

数据范围:
对于30%的数据,满足N≤10且M≤10。
对于60%的数据,满足N≤50且M≤30。
对于100%的数据,满足N≤100且M≤100,1≤T≤100,2≤K≤8,0≤ti≤1440。
数据保证随机且无误。

后记

achen:“什么?!我的罪恶の手才100只???出题人你在逗我,数据范围应该是M<=10^6!”

Source

Bill_Yang改编自ZOJ

第一届Bashu水王争霸赛

未参加
状态
已结束
规则
OI
题目
3
开始于
2017-08-25 10:00
结束于
2017-08-26 10:00
持续时间
24.0 小时
主持人
参赛人数
13