Editorial for Biến đổi số

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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;
}

Comments

There are no comments at the moment.