[Solution] Ball Sequence CodeChef Solution

Problem

There is an infinite line of people, with person numbered $(i+1)$ standing on the right of person numbered $i$. Chef can do $2$ types of operations to this line of people:

• Type $1$: Give a ball to the person number $1$.
  If there exits a person with two balls, they drop one ball and give the other ball to the person on their right, and this repeats until everyone has at most $1$ ball.
• Type $2$: Everyone gives their ball to the person on their left simultaneously. Since there is no one to the left of person $1$, they would drop their original ball if they have one.

Chef gives a total of $N$ instructions, out of which $K$ instructions are of type $2$.
Each instruction is numbered from $1$ to $N$. The indices of instructions of type $2$ are given by the array $A_1, A_2, \dots, A_K$. The rest operations are of type $1$.

Find the number of balls that have been dropped by the end of all the instructions.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• 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 total number of operations and number of operations of type $2$.
  • The next line contains the array $K$ space-separated integers $A_1, A_2, \dots, A_K$ - the indices of instructions of type $2$.

Output Format

For each test case, output on a new line the number of balls that have been dropped by the end of all the instructions.

Explanation:

Test case $1$: The operations are performed as follows:

• Type $1$: Only person $1$ has a ball. Till now, $0$ balls dropped.
• Type $1$: Person $1$ has $2$ balls. So he drops $1$ ball and passes $1$ to its right. Now, only person $2$ has a ball. Till now, $1$ ball dropped.
• Type $2$: Person $2$ passes the ball to its left. Now, only person $1$ has a ball. Till now, $1$ ball dropped.
• Type $2$: Person $1$ drops the ball. Till now, $2$ balls dropped.
• Type $1$: Only person $1$ has a ball. Till now, $2$ balls dropped.

In total, $2$ balls are dropped.

Test case $2$: Only one operation occurs which is of type $2$, so no balls are dropped.