GUPTA MECHANICAL

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

Wednesday 10 August 2022

[Solution] Copy and Paste CodeChef Solution



Problem

Chef has binary string A of length N. He constructs a new binary string B by concatenating M copies of A together. For example, if A = \texttt{"10010"}M = 3, then B = \texttt{"100101001010010"}.

Chef calls an index i (1 \le i \le N \cdot M) good if:

  • pref_i = suf_{i + 1}.

Here, pref_j = B_1 + B_2 + \ldots + B_j and suf_j = B_{j} + B_{j + 1} + \ldots + B_{N \cdot M} (Note that suf_{N \cdot M + 1} = 0 by definition)

Chef wants to find the number of good indices in B. Can you help him do so?

Input Format

  • The first line contains a single integer T — the number of test cases. Then the test cases follow.

Solution Click Below:-  👉CLICK HERE👈
👇👇👇👇👇

  • The first line of each test case contains two space-separated integers N and M — the length of the binary string A and the number of times A is concatenated to form $
  • The second line of each test case contains a binary string A of length N containing 0s and 1s only.

Output Format

For each test case, output the number of good indices in B.


Explanation:

Test case 1: B = \texttt{"0000"}. In this string, all the indices are good.

Test case 2: B = \texttt{"11111111"}. In this string, only i = 4 is good.

Test case 3: B = \texttt{"101101101"}. In this string, i = 4 and i = 5 are good.

No comments:

Post a Comment