ちょうどの場合

まず、整数 \(B\) に対してちょうど \(C\) 円を使って作れる整数は何かを考えます。

具体的な操作の列を考えて、その中から、 \(1\) を引く操作のうちひとつに注目してみます。 その操作をしなかった場合と比べて、最終的な整数がどう変化するかを見ると、次のことが分かります。

• その操作後に \(-1\) 倍を奇数回行っている場合 、操作によって最終的な数は \(1\) 増える。
• その操作後に \(-1\) 倍を偶数回行っている場合 、操作によって最終的な数は \(1\) 減る。

よって、\(-1\) 倍する操作を全くしない場合を除けば、最初に \(-1\) 倍の操作をまとめて行ったあと、 最後に \(1\) を足す操作と引く操作をどちらも \(2\) 円でできるとみなすことができます。

\(C\) が奇数

整数 \(n\) を使って\(C=2n+1\) と書けます。

\(1\) を引く操作で使われる金額の合計は常に偶数円なので、 \(-1\) 倍する操作は奇数回行う必要があります。 奇数回の操作のあと、すぬけくんの持っている整数は \(-B\) になります。 \(-1\) 倍する操作は奇数回であれば何度行っても良いため、最後に \(1\) を足し引きする回数は \(n\) 回以下なら何回でも良いです。

よって、\(-B-n\) 以上 \(-B+n\) 以下の整数がすべて作れます。

\(C\) が偶数

整数 \(n\) を使って\(C=2n\) と書けます。 \(C=0\) である場合は、\(B\) だけが作れます。 以下、\(C>0\)　（つまり、\(n>0\) ） とします。

奇数の場合と同様の理由で、\(-1\) 倍は偶数回行う必要があります。

\(-1\) 倍を全くしない場合、\(B-n\) が作れます。

\(-1\) 倍をする場合でも、偶数回の操作のあと、すぬけくんの持っている整数は \(B\) のままです。 \(-1\) 倍する操作は正の偶数回であれば何度行っても良いため、最後に \(1\) を足し引きする回数は \(n-1\) 回以下なら何回でも良いです。 よって、\(B-n+1\) 以上 \(B+n-1\) 以下の整数がすべて作れます。

以上から、\(B-n\) 以上 \(B+n-1\) 以下の整数がすべて作れます。

問題の解法

ちょうどの場合の結果を観察すると、\(C=k\) の場合に作れる数は、どれも \(C=k+2\) のときに作れることが分かります。 よって、\(C\) 円ちょうどの場合と、\(C-1\) 円ちょうどの場合に作れる数を考えれば十分です。

\(C\) 円ちょうどで作れる数が \(a\) 以上 \(b\) 以下であり、 \(C-1\) 円ちょうどで作れる数が \(c\) 以上 \(d\) 以下であるとします。

\(C\) 円ちょうどで作れる数は \(b-a+1\) 通りであり、\(C-1\) 円ちょうどで作れる数は \(d-c+1\) 通りです。 これらの共通部分のサイズは \(\max(0, \min(b,d)-\max(a,c)+1)\) で求められるため、答えは以下のとおりです。

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

C++による実装例

Pythonによる実装例