SUBAADDB - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have a string of length N.
While it has length \ge A, you will remove some substring from the string whose length is A, and insert a substring whose length is B.

Find the final length of the string.

EXPLANATION:

Let N be the length of the string.

Then, the process tells us that:

  • If N \ge A,
    • Delete a substring of length A from the string.
      This will reduce the length by A.
    • Then, insert a substring of length B into the string.
      This will increase the length by B.
  • So, the length of the string changes from N to (N - A + B).
  • Then, repeat this process with the new length.

The above algorithm can be implemented directly using a while loop, as follows:

while (n >= a) {
    n = (n - a + b);
}

Because it’s guaranteed that A \lt B, this will result in the value of N strictly reducing.

So, after several steps the value will certainly fall below A, and then the process will terminate.

Implementing this loop directly will give AC.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n, a, b = map(int, input().split())
    
    while n >= a:
        n = (n - a + b)
    print(n)