[AtCoder] ABC 158 C – Tax Increase

問題

方針

消費税を題材にした問題ですね。全探索をするのが楽ですが、ここでは別の解き方をしようと思います。

\( A \) に着目

\( A \) に着目すると、

\[ \left \lfloor \dfrac{8x}{100} \right \rfloor = A\]

を満たす \( x \) を求めれば良いので、\( x = 25a + b \ (0 \leq b \leq 24)\) とすると、

  • \( 0 \leq b \leq 12 \) のとき

\[\left \lfloor \dfrac{2x}{25} \right \rfloor = 2a\]

  • \( 13 \leq b \leq 24 \) のとき

\[\left \lfloor \dfrac{2x}{25} \right \rfloor = 2a + 1\]

となります。ここで、\( a = \left \lfloor \dfrac{A}{2} \right \rfloor \) とすると、\( A \) だけについて解くと、最小の価格は、

\[ x = 25a + 13 \times (A \bmod 2)\]

となります。

\( B \) に着目

ここで、\( a = \left \lfloor \dfrac{A}{2} \right \rfloor \) とします。上記より、取りうる価格の最小値は \( 25a \) なので、

\[B – \left \lfloor \dfrac{25a}{10} \right \rfloor < 0\]

であるとき、条件を満たす価格は存在しません。

\( A \) が偶数のとき

価格の候補は、\(x =  25a + b \ ( 0 \leq b \leq 12)\) となるので、\( 10 \%\) の消費税を考えると、

\[ \left \lfloor \dfrac{x}{10} \right \rfloor = \left \lfloor \dfrac{25a}{10} \right \rfloor + \left \lfloor \dfrac{25a \bmod 10 + b}{10} \right \rfloor \]

となります。上記の右辺の第 \( 2 \) 項の値は、\( 0 \leq 25a \bmod 10 \leq 5 \) となるので、

\[ 0 \leq \left \lfloor \dfrac{25a \bmod 10 + b}{10} \right \rfloor  \leq 1\]

となります。したがって、

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor =  0\) のとき

求める価格は \( 25a \) となります。

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor =  1\) のとき

求める価格は \( 25a + 10 – 25a \bmod 10 \) となります。

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor >  1\)

条件を満たす価格は存在しません。

\( A \) が奇数のとき

価格の候補は、\(x =  25a + b \ ( 13 \leq b \leq 24)\) となるので、偶数の場合と同様に考えると、

\[ 1 \leq \left \lfloor \dfrac{25a \bmod 10 + b}{10} \right \rfloor  \leq 2\]

となります。

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor =  0\) のとき

条件を満たす価格は存在しません。

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor =  1\) のとき

求める価格は \( 25a + 13 \) となります。

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor =  2\)

求める価格は \( 25a + 20 –  25a \bmod 10\) となります。

  • \(B – \left \lfloor \dfrac{25a}{10} \right \rfloor >  2\)

条件を満たす価格は存在しません。

コード

類似問題