Hướng dẫn cho Biến đổi số
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Spoiler Alert
Hint 1
- Phân tích \(N\) chia hết cho 30
\(\Leftrightarrow\) \(N\) chia hết 3 và \(N\) chia hết 10 (vì (10, 3) là cặp số nguyên tố cùng nhau)
Hint 2
- Vì \(N\) chia hết cho 10
Nếu trong số \(N\) không có chữ số 0 ta loại
Nếu có thì ta đặt chữ số 0 ở cuối
Hint 3
- Vì \(N\) chia hết cho 3
Nếu tổng các chữ số không chia hết 3 ta loại
Ngược lại thì dù hoán đổi chữ số nào thì tổng chữ số vẫn không thay đổi
Hint 4
- Vì \(N\) lớn nhất, và dựa vào 2 ý trên
Ta sắp xếp các chữ số của \(N\) giảm dần
Nếu chữ số cuối của \(N\) khác 0 hay tổng các chữ số \(N\) khác 0 thì ta loại
Reference AC code | \(O(log_{10}n\) \(\times\) \(log_2(log_{10}n))\) time | \(O(n)\) auxiliary space | Sorting, String
C++
int main()
{
/// Nhận số N dưới dạng xâu các chữ số
string s;
cin >> s;
/// Sắp xếp các chữ số
sort(s.begin(), s.end(), greater<char>());
int summod = 0; /// Tính chia hết cho 3 của tổng
for (char c : s) summod = (summod + c - '0') % 3;
if (summod != 0 || s.back() != '0') cout << -1; /// Nếu số không thỏa mãn
else cout << s; /// Ngược lại xuất số lớn nhất
return 0;
}
Another Approach
- Online Solving
Nhận từng chữ số thay vì nhận cả xâu
Thay vào đó bạn dùng mảng \(f[x]\) là tần số chữ số \(x\) xuất hiện trong xâu
Reference AC code | \(O(n)\) time | \(O(n)\) auxiliary space |
C++
inline bool isDigit(char c) { return '0' <= c && c <= '9'; } /// Nếu c là chữ số
int main()
{
vector<int> f(10, 0); /// Mảng tần số
for (char c; isDigit(c = getchar()); f[c - '0']++); /// Đếm tần số
int sum = 0; /// Tính tổng chữ số
for (int i = 0; i < 10; ++i) sum += i * f[i]; /// sum = Tổng các giá trị của số * tần số xuất hiện
if (f[0] == 0 || sum % 3 != 0) return cout << -1, 0; /// Nếu N không thỏa mãn
for (int i = 9; i >= 0; --i) /// Duyệt ngược từ chữ số lớn nhất
while (f[i]--) /// Nhận bao nhiêu thì dùng bấy nh
cout << i; /// Xuất ra kết quả
return 0;
}
Bình luận