Exactly \(C\) yen

First, what can we make from an integer \(B\) using exactly \(C\) yen?

Let us consider a specific sequence of operations and focus on an operation that subtracts \(1\). Ultimately, that operation has the following effect on the final number:

• if we multiply the number by \(-1\) an odd number of times later, the subtraction increases the final number by \(1\);
• if we multiply the number by \(-1\) an even number of times later, the subtraction decreases the final number by \(1\).

Thus, except when we never multiply the number by \(-1\), we can assume we can do all multiplications in the beginning to make both addition and subtraction available for \(2\) yen.

When \(C\) is odd

We can write \(C=2n+1\) with an integer \(n\).

Since the subtractions always cost an even number of yen in total, we need to do the multiplication an odd number of times. After that, Snuke’s integer becomes \(-B\). We can do the multiplication any odd number of times, so we can do the addition and subtraction in the end any number of times not exceeding \(n\).

Thus, we can make every integer from \(-B-n\) through \(-B+n\).

When \(C\) is even

We can write \(C=2n\) with an integer \(n\). If \(C=0\), we can make \(B\) only. Below, we assume \(C>0\) (that is, \(n>0\)).

Similarly to the “odd” case, we need to do the multiplication an even number of times.

If we never use the multiplication, we can make \(B-n\).

If we do use the multiplication, Snuke’s integer is still \(B\) after an even number of multiplications. We can do the multiplication any positive even number of times, so we can do the addition and subtraction in the end any number of times not exceeding \(n-1\). Thus, we can make every integer from \(B-n+1\) through \(B+n-1\).

Therefore, we can make every integer from \(B-n\) through \(B+n-1\).

The solution to the original problem

From the conclusions for the above case where we use exactly \(C\) yen, we can see that every number that can be made with \(C=k\) yen can also be made with \(C=k+2\) yen. Thus, we just need to consider two cases where we use exactly \(C\) yen and exactly \(C-1\) yen.

Let us say we can make the numbers from \(a\) through \(b\) with \(C\) yen and the numbers from \(c\) through \(d\) with \(C-1\) yen.

There are \(b-a+1\) numbers that can be made with \(C\) yen, and \(d-c+1\) numbers that can be made with \(C-1\) yen. The intersection of these two sets contains \(\max(0, \min(b,d)-\max(a,c)+1)\) numbers, so the answer is:

\begin{aligned} (b-a+1) +(d-c+1) -\max(0, \min(b,d)-\max(a,c)+1) \end{aligned}

Sample Implementation in C++

Sample Implementation in Python