Biến đổi số

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 640M
Input: stdin
Output: stdout

Author:
Problem types

Vào một buổi sáng, rất tình cờ Nam nhìn thấy một số nguyên dương N trên đường từ nhà đến trường. Vì Nam rất thích số \(30\) nên Nam muốn biến đổi số \(N\) thành số \(M\) có dạng là số lớn nhất và là bội của số \(30\) bằng cách thay đổi vị trí của các chữ số trong số \(N\) mà Nam nhìn thấy.

Yêu cầu: Hãy trợ giúp Nam bằng cách viết một chương trình tìm số \(M\) (nếu nó tồn tại).

Dữ liệu vào

  • Gồm 1 dòng duy nhất chứa số nguyên \(N\), số \(N\) có tối đa là \(10^5\) chữ số.

Kết quả

  • In số \(M\) vừa tìm được. Nếu không tồn tại \(M\) thì in ra \(-1\).

Sample Input

30

Sample Output

30

Sample Input

102

Sample Output

210

Sample Input

3333333333333333333333333333

Sample Output

-1

View comments (4)

Comments


  • 0
    nguyenbahoang2709  commented on 12:22 p.m. 23 oct, 2021

    for char c : s là sao vậy bạn


    • 1
      VoBaThongL921  commented on 4:33 p.m. 24 oct, 2021

      for(char c : s) chỉ là vòng for duyệt lần lượt tất cả các kí tự của xâu s thôi bạn ạ.


  • 5
    SPyofgame  commented on 10:40 a.m. 15 jun, 2020

    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
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    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 |
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    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;
    }