[AtCoder] ABC 181 D – Hachi

2020年11月1日2020年12月12日

問題

方針

\( |S| \geq 3 \) のときを考えます。自然数 \( n \) が \( 8 \) の倍数である条件は、下 \( 3 \) 桁が \( 8 \) の倍数であることと同値なので、\( 3 \) 桁の \( 8 \) の倍数が作れるかどうかを調べます。\( x \) を \( 3 \) 桁の \( 8 \) の倍数とすると、\( x \) に含まれる文字が \( S \) に含まれているかどうかを調べればいいです。これは、先に \( S \) に含まれる各数字の頻度を数えておけば高速に計算できます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    string S;
    cin >> S;
    int a[10]{};
    for (char c : S) {
        a[c - '0']++;
    }
    if (S.length() == 1) {
        if (S[0] == '8') {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return 0;
    } else if (S.length() == 2) {
        int b1 = S[0] - '0';
        int b2 = S[1] - '0';
        if ((b1 + 10 * b2) % 8 == 0 || (b2 + 10 * b1) % 8 == 0) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
        return 0;
    }
    for (int i = 100; i <= 999; i++) {
        if (i % 8 == 0) {
            int t1 = i / 100;
            int t2 = (i - 100 * t1) / 10;
            int t3 = i % 10;
            int b[10]{};
            b[t1]++;
            b[t2]++;
            b[t3]++;
            bool flag = true;
            for (int j = 0; j < 10; j++) {
                if (b[j] > a[j]) {
                    flag = false;
                }
            }
            if (flag) {
                cout << "Yes\n";
                return 0;
            }
        }
    }
    cout << "No\n";
    return 0;
}