Biến đổi số

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
admin
Dạng bài
Đ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
    voducviet500    11:14 a.m. 12 Tháng 10, 2024

    ko hiểu gì cả


    • -3
      thuannguyen1972dn    6:21 p.m. 12 Tháng 5, 2024

      python:
      n=list(input())
      n.sort(reverse=True)
      kq=""
      for i in n:
      kq+=i
      if int(kq)%30==0:
      print(kq)
      else:
      print(-1)

      1 phản hồi

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

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


        • -3
          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

          • 6
            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

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