Sleep Cycle Codechef Solution

by

Sleep Cycle Solution Problem Code: SLPCYCLE

Chef has been studying the human sleep cycle for years. He divides a day into LL units of time (numbered 11 through LL). Chef’s research shows that his body requires spending only HH continuous units of time per day on sleep — then, he can stay active during work. However, in case of travel or any other responsibilities, he might not be able to achieve this ideal state.

Next, Chef noticed that if he sleeps for xx (x<Hx<H) continuous units of time and then performs some other activity, he can still meet his daily sleep quota, but the remaining time he needs to spend on continuously sleeping becomes 2⋅(H−x)2⋅(H−x). He can further split this sleeping time in the same way, i.e. if he now sleeps for yy more (y<2⋅(H−x)y<2⋅(H−x)) continuous units of time, his required sleeping time becomes 2⋅(2⋅(H−x)−y)2⋅(2⋅(H−x)−y), and so on.

You are given a string SS with length LL; for each valid ii, the ii-th character of this string is ‘0’ if the ii-th unit of time is free (so Chef can use it to sleep) or ‘1’ if it is occupied.

Can Chef ever get enough sleep to feel fresh during his work, given that he can choose when to sleep in his free time?

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers LL and HH.
  • The second line contains a single string SS with length LL.

Output

Print a single line containing the string "YES" if Chef can have the required amount of sleep or "NO" if he cannot (without quotes).

You may print each character of each string in uppercase or lowercase (for example, the strings “yEs”, “yes”, “Yes” and “YES” will all be treated as identical).

Constraints

  • 1≤T≤101≤T≤10
  • 1≤H≤L≤1051≤H≤L≤105
  • SS contains only characters ‘0’ and ‘1’

Example Input

4
3 1
111
3 1
101
7 5
0000100
6 5
000010

Example Output

NO
YES
YES
NO

Explanation

Example case 1: Chef needs only 11 unit of sleep, but since he is busy all the time, he cannot sleep at all.

Example case 2: Chef needs only 11 unit of sleep and he has exactly one unit of time when he is free, so he can sleep during that unit of time.

Example case 3: Chef needs 55 continuous units of sleep. First, he spends the first 44 free units of time, and then he needs 2⋅(5−4)=22⋅(5−4)=2 continuous units of sleep, which he has available as the last 22 free units of time.

Example case 4: Chef needs 55 units of sleep. If he spends the first 44 units of time, he still needs 2⋅(5−4)=22⋅(5−4)=2 continuous units of sleep, but only a single unit of time is left now, so he is unable to get enough sleep.

Weekly Contest 247

Biweekly Contest 55

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

Related :

Related :

Leave a Comment

twelve − 7 =