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: