Christopher's Rainy Day
Time Limit: 5 Seconds Memory Limit: 32768 KB
As you've known in "Christopher's Key Ring" problem, Christopher
nearly spent all of his money being treated in the hospital. The only thing
left to him, is the heart filled with recollection, and fighting with tragic
Fortune's wheel. He loves animals, especially cats and dogs, so he...
Christopher's pet shop is the biggest one in XX city. It has even 250,000 pets
at the most prosperous time. One day, a rich man came to buy all of his cats
and dogs. Christopher thought this is the best time to turn over a new leaf.
But the rich man said, he'll pay money iff he sees the entire N arrived pets
in good condition.
Transporting them is a difficult problem, coz he only has N pets (dogs and cats),
none of them could be done harm. There's a train with several carriages waiting
for them. If a carriage has much more cats than dogs, or much more dogs than
cats, they might fight together (to ensure their safe, the max difference between
numbers of cats and dogs must not exceed k). Apparently a carriage with only
cats or only dogs is allowed.
The number of cats and dogs is so large that Christopher couldn't pick a single
cat or dog among them. They must get on the train one by one, from the first
carriage to the last. That is, if he's filling Xth carriage, he could put the
current pet onto the Xth carriage, or close the door of Xth carriage (make sure
this carriage is allowed depending on the above paragraph), and put it onto
the (X+1)th carriage.
Input
The first line of input contains a number X which denotes the number of test
cases. For each test case:
Line 1: 3 integer n (n <= 250,000) - number of cats and dogs, m - the capacity
of one carriage, k - the max difference between number of cats and dogs on a
single carriage. (1 <= m, k <= n)
Line 2~n+1: every line contains a character ('C' or 'D'), denotes the type of
a pet in queue.
There're NO breakline between two continuous test cases.
Output
Exact X lines, each one contains the minimal number of carriages needed.
Sample Input
2 5 4 1 C D D D C 5 4 1 C D D D C
Sample Output
2 2Submit
Source: Online Contest of Christopher's Adventure