Dogs and Cats kickstart solution- You work for an animal shelter and you are responsible for feeding the animals. You already prepared DD portions of dog food and CC portions of cat food. There are a total of NN animals waiting in a line, some of which are dogs and others are cats. It might be possible that all the animals in the line are dogs or all the animals are cats. A string SS of NN characters C and D represents the order of cats and dogs in the line. The ii-th character is equal to C if the ii-th animal in the line is a cat. Similarly, the ii-th character is equal to D if the ii-th animal in the line is a dog.

Dogs and Cats kickstart solution

Problem

You work for an animal shelter and you are responsible for feeding the animals. You already prepared DD portions of dog food and CC portions of cat food.

There are a total of NN animals waiting in a line, some of which are dogs and others are cats. It might be possible that all the animals in the line are dogs or all the animals are cats. A string SS of NN characters C and D represents the order of cats and dogs in the line. The ii-th character is equal to C if the ii-th animal in the line is a cat. Similarly, the ii-th character is equal to D if the ii-th animal in the line is a dog.

The animals are fed in the order they stay in the line. Each dog eats exactly 11 portion of dog food and similarly each cat eats exactly 11 portion of cat food. Moreover, you have extra portions of cat food. Every time a dog eats food, you bring MM extra portions of cat food for cats.

Animals have to be fed in the order they wait in line and an animal can only eat if the animal before it has already eaten. That means that if you run out of dog (or cat) food portions and a dog (or a cat) is about to get fed, the line will not move, as all the animals will wait patiently.

You need to determine if in this scenario all the dogs in the line will be fed. Note that this means that some cats might remain in the line, but worry not, you will eventually feed them later!

Input

Dogs and Cats solution kickstart

The first line of the input gives the number of test cases, TTTT test cases follow.

The first line of each test case contains four integers NNDDCC, and MM: the number of animals, the initial number of dog food portions, the initial number of cat food portions, and the additional portions of cat food that we add after a dog eats a portion of dog food, respectively.

The next line contains a string SS of length NN representing the arrangement of animals.

Output

Dogs and Cats solution kickstart

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 11) and yy is YES if all the dogs will be fed and NO otherwise.

Limits

Dogs and Cats solution kickstart

Memory limit: 1 GB.
1T1001≤T≤100.
1N1041≤N≤104.
0D,C1060≤D,C≤106.
SS consists of only characters C and D.

Test Set 1

Time limit: 20 seconds.
M=0M=0

Test Set 2

Time limit: 40 seconds.
0M1060≤M≤106.

Sample

Dogs and Cats solution kickstart

Note: there are additional samples that are not run on submissions down below.

Sample Input

content_copy

Dogs and Cats solution kickstart

 

3
6 10 4 0
CCDCDD
4 1 2 0
CCCC
4 2 1 0
DCCD
Sample Output

save_alt

Dogs and Cats solution kickstart

Case #1: YES
Case #2: YES
Case #3: NO

In Sample Case #1, there are 1010 portions of dog food and 44 portions of cat food.

  1. The first two animals are cats, so after they eat, 22 portions of cat food remain.
  2. Then a dog eats one portion of dog food. Now, there are 99 portions of dog food left.
  3. Next, a cat eats a portion of cat food, reducing the number of portions of cat food to 11.
  4. The last two animals are dogs and they each eat one portion of dog food.

So in this case, all the dogs are able to eat.

Dogs and Cats solution kickstart

In Sample Case #2, there are no dogs. Hence, all (zero) dogs will be able to eat trivially.

In Sample Case #3, the cat before the second dog will not be able to eat because there will not be enough portions of cat food. Hence, the second dog will also not eat.

 

Additional Sample – Test Set 2

Dogs and Cats solution kickstart

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input
content_copy
2
12 4 2 2
CDCCCDCCDCDC
8 2 1 3
DCCCCCDC
Sample Output

save_alt

Dogs and Cats solution kickstart

 

content_copy
Case #1: YES
Case #2: NO

In Sample Case #1, 22 portions of cat food appear whenever a dog eats a portion of dog food.

  1. After the first cat eats, there is 11 portion of cat food left.
  2. Then a dog eats, leaving 33 portions of dog food and 33 portions of cat food.
  3. After the next 33 cats eat, there are 33 portions of dog food and 00 portions of cat food remaining.
  4. Then a dog eats, leaving 22 portions of dog food and 22 portions of cat food.
  5. After the next 22 cats eat food, there are 22 portions of dog food and 00 portions of cat food left.
  6. Now a dog eats, leaving 11 portion of dog food and 22 portions of cat food.
  7. Next a cat eats, leaving 11 portion of dog food and 11 portion of cat food.
  8. The last dog eats the remaining portion of dog food.

So in this case, all the dogs are able to eat.

Dogs and Cats solution kickstart

In Sample Case #2, the cat before the second dog will not be able to eat because there will not be enough portions of cat food.

Leave a Comment