CLB THTDCA Tin| Số nhỏ nhất chia hết cho 6, THTA Sơ khảo Hà Nội Bài 5, 2025

Tác giả:

Small, nguyennguyen2609, phuctinhoctre2025

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: 1100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một số tự nhiên có không quá \(100\) chữ số. Bạn được phép sắp xếp lại các chữ số này để tạo thành một số mới (không chứa số \(0\) không có nghĩa ở đầu). Hãy tìm số nhỏ nhất có thể tạo ra mà chia hết cho \(6\).

Input

Một dòng ghi xâu ký tự số gồm không quá \(100\) chữ số.

Output

Một dòng ghi số nhỏ nhất chia hết cho \(6\) tạo được, hoặc ghi \(0\) nếu không có cách nào.

Example

Test 1

Input

Output

Note

Chỉ có một cách sắp xếp duy nhất số \(36\) chia hết cho \(6\).

Test 2

Input

Output

Note

Không thể tạo số chia hết cho \(2\) (vì không có chữ số chẵn) nên không thể chia hết cho \(6\). Kết quả là \(0\).

Test 3

Input

Output

Note

Có nhiều cách tạo số chia hết cho \(6\) như \(3600, 3060, 6300, 6030, \dots\). Trong đó \(3006\) là số nhỏ nhất thỏa mãn.

Scoring

Subtask \(1\) (\(30\%\) số điểm): Dãy số không chứa chữ số \(0\).
Subtask \(2\) (\(70\%\) số điểm): Không ràng buộc gì thêm.

Bình luận (1)

Tải bình luận...