Chia hết 36 (THT B Vòng Sơ loại Toàn quốc 2026 - Lần 2)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small, LeNam2021
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1400 (p) Thời gian: 0.25s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một số tự nhiên \(N\). Bạn được phép hoán vị (sắp xếp lại) vị trí các chữ số của \(N\) để tạo thành một số tự nhiên mới.

Yêu cầu

Hãy tìm số tự nhiên có giá trị nhỏ nhất có thể tạo thành sao cho số đó chia hết cho \(36\) và không có chữ số \(0\) vô nghĩa ở đầu. Nếu không thể tạo ra bất kỳ số nào thỏa mãn điều kiện, hãy in ra \(-1\).

Input

  • Gồm một dòng duy nhất chứa số tự nhiên \(N\). Số lượng chữ số của \(N\) nằm trong khoảng từ \(1\) đến \(10^5\) chữ số.

Output

  • Ghi ra một số duy nhất là kết quả của bài toán (số nhỏ nhất chia hết cho \(36\) được tạo thành). Nếu không tồn tại số thỏa mãn, in ra \(-1\).

Example

Test 1

Input 
432
Output 
324
Note

Các chữ số ban đầu là \(2, 3, 4\). Các số tự nhiên có thể tạo thành từ \(3\) chữ số này là: \(234, 243, 324, 342, 423, 432\). Trong đó, chỉ có số \(324\) và \(432\) là chia hết cho \(36\). Số có giá trị nhỏ nhất là \(324\).

Test 2

Input 
30312
Output 
10332
Note

Số nhỏ nhất được tạo thành từ các chữ số \(0, 1, 2, 3, 3\), không có chữ số \(0\) đứng đầu và chia hết cho \(36\) là \(10332\) (vì \(10332 = 36 \cdot 387\)).

Test 3

Input 
123
Output 
-1
Note

Không có cách sắp xếp để tạo ra số chia hết cho \(36\). Kết quả là \(-1\).

Constraints

  • Có \(80\%\) số test tương ứng với \(80\%\) số điểm thỏa mãn: Giá trị của \(N \leq 10^9\).
  • \(20\%\) số test còn lại tương ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: