GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday, 5 October 2022

[Solution] Alternative Sufferings CodeChef Solution



Problem

You are given a binary string S.

In one second, the following scenario happens simultaneously and independently for all the bits which are set to 1 in the string:

  • Change the bit from 1 to 0.
  • If the left neighbour exists and is 0, change it to 1.
  • If the right neighbour exists and is 0, change it to 1.

For example, if S = 010 initially, then after 1 second, S = 101 (the 1 bit and both its neighbours were changed). After another second, S = 010. Here, the first and the last bit were changed to 0 because earlier they were 1. The middle bit was changed because it was 0 earlier and it was a neighbour of a 1 bit.

Find out the string S after K seconds.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains two space-separated integers N and K — the length of string S and the number of seconds.
Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

    • The next line describes the string S.

Output Format

For each test case, output the string S after exactly K seconds.


Explanation:

Test case 1: The middle bit is changed to 1 since it had a neighbouring set bit (in this case both left and right) and both the set bits are changed to 0. Hence, after one second, it is 101.

Test case 2: After first second, the string S will be 01010. After another second , the string becomes 10101.

No comments:

Post a Comment