F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 1314. -- River过河

1314: River过河

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 72  Solved: 24
[Submit][Status][Discuss]

Description

ZY带N个小Kid过河,小KID分成两种:高一年级,高二年级,由于存在代沟问题,如果同一条船上高一年级生和高二年级
生数量之差超过K,就会发生不和谐的事件.当然如果一条船上全是同一年级的,就绝对不会发生争执.现在ZY按小KID
队列的顺序依次安排上船,并且不能让他们在过河时发生争执.对于当前等待上船的小KID来说,要么让他上船,要么
将停在渡口的船开走,再让他上另一条船,同一条船上的人不过超过M人.为了让所有的小KID过河,在知悉小KID队列
的情况下,最少需要多少条船.

Input

第一行给出N,M,K.含义如上所述 
下行N行用来描述小KID的队列,每行一个字符”A”或者”L”
1<=N<=250000,1<=M,K<=N

Output

最少需要多少条船

Sample Input

5 4 1
A
L
L
L
A

Sample Output

2

HINT

Source

[Submit][Status][Discuss]

HOME Back