Biến đổi số

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

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.

Bạn hãy hỗ trợ Nam bằng cách viết chương trình để tìm số \(M\) (nếu nó tồn tại).

Input

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

Output

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

Example

Test 1

Input
30 
Output
30

Test 2

Input
102
Output
210

Test 3

Input
3333333333333333333333333333 
Output
-1

Bình luận


  • -1
    nguyennhatnam123 4:08 p.m. 6 Tháng 6, 2023

    bai kho v


    • -1
      nguyenbahoang2709 12:22 p.m. 23 Tháng 10, 2021

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

      1 phản hồi

      • 7
        SPyofgame 10:40 a.m. 15 Tháng 6, 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

        • \(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

        • \(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

        • \(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;
        }