HSG lớp 12 Tỉnh Thanh Hóa 2023 - Bài 3 - Mật mã

Trên vách đá có ghi rất nhiều các con số bí ẩn mà chúng có mối liên hệ với con số 30. Sau một thời gian nghiên cứu, các chuyên gia đã tìm cách giải mã các số đó như sau: Hoán vị các chữ số của số bí ẩn để thu được một bội số lớn nhất của 30. Hãy viết chương trình để giúp các chuyên gia giải mã các số bí ấn đó.

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên dương \(N\), với \(N\) có tối đa \(10^7\) chữ số cần giải mã.

Dữ liệu ra

• Một số duy nhất là số lớn nhất chia hết cho 30, tìm được bằng cách hoán vị các chữ số của \(N\). Nếu không tìm thấy thì đưa ra \(-1\)(âm một)

Ví dụ