[yukicoder] No. 0928 軽減税率？
問題
https://yukicoder.me/problems/no/928方針
関数 \( 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 \) の範囲を全探索すれば良いです。
コード
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll my_pow(ll x, ll n) {
if (n == 0) return 1;
if (n % 2 == 0) return my_pow(x * x, n / 2);
return x * my_pow(x, n - 1);
}
int main() {
ll P, Q, A;
cin >> P >> Q >> A;
ll t = my_pow(10, 9);
if (P == Q) {
if (A == 0) {
cout << "0\n";
} else {
cout << t << "\n";
}
return 0;
}
if (Q < P && A == 0) {
cout << "0\n";
return 0;
}
if (P < Q) {
if (A != 0) {
cout << t << "\n";
} else {
int k = 0;
for (ll x = 1; x <= 99; x++) {
ll p = (100 + P) * x / 100;
ll q = (100 + Q) * x / 100 + A;
if (p >= q) k++;
}
cout << t - k << "\n";
}
return 0;
}
int cnt = 0;
for (ll x = 1; x <= 1000000; x++) {
ll p = (100 + P) * x / 100;
ll q = (100 + Q) * x / 100 + A;
if (p < q) cnt++;
}
cout << cnt << "\n";
return 0;
}