Official

D - Hachi Editorial by evima


The problem asks to determine if any of permutations is a multiple of \(8\), so let us consider how to determine if an integer is divisible by \(8\).

Since \(1000 = 8 \times 125\), \(10^3,10^4,10^5\dots\ \) are all multiples of \(8\), so we determine only if the last three digits are a multiple of \(8\).

By examining if \(000, 008, 016, \dots, 976, 984, 992\), the candidates of last three digits to form a multiple of \(8\), can be constructed, the problem can be solved in a total of \((O|S|)\) time.

Be careful when \(|S| \leq 2\).

Sample Code (C++)

#include <bits/stdc++.h>
using namespace std;
 
bool solve(string s){
    if(s.size() == 1) return s == "8";
    if(s.size() == 2){
        if(stoi(s) % 8 == 0) return 1;
        swap(s[0], s[1]);
        return stoi(s) % 8 == 0;
    }
    vector<int> cnt(10);
    for(char x : s) cnt[x - '0']++;
    for(int i = 112; i < 1000; i += 8){
        auto c = cnt;
        for(char x : to_string(i)) c[x - '0']--;
        if(all_of(c.begin(), c.end(), [](int x){ return x >= 0; })) return 1;
    }
    return 0;
}
int main(){
    string s;
    cin >> s;
    puts(solve(s) ? "Yes" : "No");
}

Sample Code (Python)

from collections import Counter

n = input()

if len(n) <= 2:
    if int(n) % 8 == 0 or int(n[::-1]) % 8 == 0:
        print("Yes")
    else:
        print("No")
    exit()

cnt = Counter(n)

for i in range(112, 1000, 8):
    if not Counter(str(i)) - cnt:
        print("Yes")
        exit()

print("No")

posted:
last update: