[yukicoder] No. 0928 軽減税率?

問題

方針

関数 \( f(x) \) を持ち帰りと店内の料金の差とすると、次のように計算できます。

\[ \begin{eqnarray}
f(x) &=& A + \left \lfloor \dfrac{100 + Q}{100}x \right \rfloor – \left \lfloor \dfrac{100 + P}{100}x \right \rfloor\\
&=& A + \left \lfloor \dfrac{Q}{100}x \right \rfloor – \left \lfloor \dfrac{P}{100}x \right \rfloor
\end{eqnarray}\]

これは、\( \left \lfloor \dfrac{100 + Q}{100}x \right \rfloor = x + \left \lfloor \dfrac{Q}{100}x \right \rfloor \) となるので、上記のように計算できます。\( f(x) > 0 \) となる \( x \) の個数が答えになります。

\( P = Q \) のとき

このとき、\( f(x) = A \) となるので、\( A = 0 \) ならば、答えは \( 0 \) であり、\( A \neq 0 \) ならば、\( 10^9 \) となります。

\( P < Q \) のとき

\( a, b \) を整数として、\( x = 100a + b \ (0 \leq b \leq 99) \) 表現します。このとき、

\[f(x) = f(a, b) = A + (Q – P)a +\left \lfloor \dfrac{Q}{100}b \right \rfloor – \left \lfloor \dfrac{P}{100}b \right \rfloor\]

となるので、\( f(a, b) > 0\) を考えると、

\[A + (Q – P)a > \left \lfloor \dfrac{P}{100}b \right \rfloor – \left \lfloor \dfrac{Q}{100}b \right \rfloor\]

となります。右辺に注目すると、\( P < Q \) より、

\[ \left \lfloor \dfrac{P}{100}b \right \rfloor – \left \lfloor \dfrac{Q}{100}b \right \rfloor \leq 0 \]

となります。

\( A = 0 \) のとき

このとき、\( Q – P > 0 \) より、\( a \neq 0 \) ならば不等式を満たすので、\( 1 \leq x \leq 99 \) の中で条件を満たさないものの数を \( k \) とすると、答えは \( 10^9 – k \) となります。

\( A \neq 0 \) のとき

このとき、\( f(a, b) > 0\) なので、\( 10^9 \) が答えとなります。

\( Q < P \) のとき

上記と同様にして、\( f(a, b) > 0\) を考えると、

\[A – (P – Q)a > \left \lfloor \dfrac{P}{100}b \right \rfloor – \left \lfloor \dfrac{Q}{100}b \right \rfloor\]

の右辺は、

\[ \left \lfloor \dfrac{P}{100}b \right \rfloor – \left \lfloor \dfrac{Q}{100}b \right \rfloor \geq 0 \]

となるので、\( A – (P – Q)a \geq 1\) を満たす必要があります。よって、

\[ a \leq \dfrac{A-1}{P-Q}\]

となります。ここで、\( a \) の最大値を考えると、\( P – Q = 1 \wedge A = 10^4\) のとき、\( a = 10^4 – 1 \) となります。\( x = 100a +b \) なので、\( 1 \leq x \leq 10^6 \) の範囲を全探索すれば良いです。

コード