Symphony of the Kettles

View as PDF

Submit solution

Points: 0.30 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Henya is a genius. Everyone loves Henya, not only because she has an IQ of ~999~, but also because she can create the sound of boiling water kettles with her lovely voice, which is very pleasant to hear.

With her intelligence, Henya has many quirky but interesting ideas. On a boring day, Henya invented a music band with only kettles! Henya has ~n~ kettles, with some kettles currently turned on and some turned off. Henya said that when all the kettles are turned on, they will boil at the same time and then a perfect symphony will be played.

As a fan of Henya, you really want to hear this symphony. Therefore, Henya challenges you to turn on all the kettles with only the following operations (zero or more times):

  • Choose at least ~a~ and at most ~b~ kettles arbitrarily and change the state of these kettles (turn on to turn off or vice versa).

Check if you can turn on all the kettles with the operations that Henya has proposed.


The first line contains a positive integer ~t~ (~1 \leq t \leq 100~) — the number of test cases. The description of each test case is as follows.

The first line contains three positive integers ~n~, ~a~, ~b~ (~1 \leq a \leq b \leq n \leq 100~) — the number of Henya's water kettles and the minimum and maximum number of kettles that you can change the state in each operation.

The second line contains a binary string ~s~ of length ~n~.

  • ~s_i = 0~ means that the ~i~-th kettle is initially turned off,

  • otherwise ~s_i = 1~ means that the ~i~-th kettle is initially turned on.


For each test case, print "YES" (without quotes) if you can turn on all the kettles and enjoy the symphony. Otherwise, print "NO" (without quotes).


The score for this problem is ~1000~ points.

Sample Input 1

7 3 4
3 3 3
3 2 3

Sample Output 1



In the first example, you can turn on the first ~3~ kettles, then turn on the last ~4~ kettles.

In the second example, you can only choose all ~3~ kettles and change their states. When you change the state for the first time, you will get the state of the kettles as 010. After the second time, you will get the state of the kettles as 101 – this is the initial state. Therefore, there is no way to turn on all the kettles.

In the third example, you are allowed to choose at least ~2~ kettles to change their states. You can perform the following operations, with the chosen kettles being underlined:

$$\underline{\texttt{1}}\texttt{0}\underline{\texttt{1}} \rightarrow \underline{\texttt{0}\texttt{0}\texttt{0}} \rightarrow \texttt{111}$$


Please read the guidelines before commenting.

There are no comments at the moment.