[AtCoder] ABC 158 C – Tax Increase

2020年3月8日2020年12月15日

問題

方針

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

\( 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\)

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

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int A, B;
    cin >> A >> B;
    int a = A / 2;
    int d = 25 * a % 10;
    int t = B - 25 * a / 10;
    if (t < 0) {
        cout << "-1\n";
        return 0;
    }
    if (A % 2 == 0) {
        if (t == 0) {
            cout << 25 * a << "\n";
        } else {
            if (t > 1) cout << "-1\n";
            else {
                cout << 25 * a + 10 - d << "\n";
            }
        }
    } else {
        if (t == 0 || t > 2) {
            cout << "-1\n";
            return 0;
        }
        if (t == 1) {
            cout << 25 * a + 13 << "\n";
        } else {
            cout << 25 * a + 20 - d << "\n";
        }
    }
    return 0;
}

類似問題