Tóm tắt đề bài

Cho một số tự nhiên \(N\) (dạng chuỗi) chỉ gồm các chữ số từ 1 đến 9, độ dài không quá \(10^4\). Ta được phép xóa một số chữ số (có thể không xóa), giữ nguyên thứ tự các chữ số còn lại để tạo thành một số mới. Hãy tìm số chia hết cho 3 và có giá trị lớn nhất có thể. Nếu không tạo được số nào chia hết cho 3 thì in 0.

Phân tích

• Khi xóa chữ số và giữ nguyên thứ tự, số tạo được là một dãy con (subsequence) của chuỗi \(N\).
• Điều kiện chia hết cho \(3\):
  • Một số chia hết cho \(3\) khi và chỉ khi tổng các chữ số của nó \(\bmod\ 3 = 0\).
• Mục tiêu “giá trị lớn nhất” với số có thể rất dài:
  • Số có nhiều chữ số hơn luôn lớn hơn.
  • Nếu cùng độ dài, so sánh theo từ điển (lexicographic) vì không có chữ số 0 và không có số âm, chuỗi lớn hơn từ điển tương ứng số lớn hơn.
• Ràng buộc \(|N| \le 10^4\) gợi ý dùng quy hoạch động với số trạng thái nhỏ (chỉ theo phần dư mod 3).

Hướng giải quyết

Ý tưởng DP theo phần dư mod 3

Ta duyệt từng chữ số từ trái sang phải, và duy trì:

• dp[r]: chuỗi tốt nhất (lớn nhất theo tiêu chí) có tổng chữ số \(\bmod\ 3 = r\) sau khi xét một prefix nào đó.

Khởi tạo:

• dp[0] = "" (chuỗi rỗng có tổng \(0\))
• dp[1] = None, dp[2] = None (chưa tạo được)

Khi xét chữ số ch (giá trị \(d\)), ta có hai lựa chọn:

1. Bỏ qua ch: trạng thái không đổi.
2. Chọn ch:
   • Từ mỗi dp[r] hiện có, tạo chuỗi mới dp[r] + ch với phần dư mới \((r + d) \bmod 3\).
3. Ngoài ra có thể bắt đầu chuỗi mới chỉ với ch (tức là subsequence bắt đầu tại đây).

Để chọn “tốt nhất” giữa hai ứng viên chuỗi, dùng hàm so sánh:

• Chuỗi nào dài hơn thì tốt hơn.
• Nếu cùng dài, chuỗi nào lớn hơn từ điển thì tốt hơn.

Vì sao tiêu chí này đúng?

Ta cần số lớn nhất:

• Ưu tiên độ dài: mọi số có nhiều chữ số hơn đều lớn hơn số có ít chữ số hơn.
• Nếu cùng độ dài: so sánh từng chữ số từ trái sang phải chính là so sánh từ điển.

Thuật toán (đúng như code AC)

1. Đọc \(N\) dạng chuỗi.
2. Khởi tạo dp = ["", None, None].
3. Với mỗi ký tự ch trong \(N\):
   • Sao chép new_dp = dp[:] để mặc định “không chọn ch”.
   • Với mỗi \(r \in \{0,1,2\}\) nếu dp[r] tồn tại:
     • new_r = (r + d) % 3
     • cập nhật new_dp[new_r] bằng chuỗi tốt hơn giữa hiện tại và dp[r] + ch.
   • Cập nhật trường hợp bắt đầu mới: new_dp[d % 3] với ch.
   • Gán dp = new_dp.
4. Kết quả là dp[0]:
   • Nếu dp[0] == "" (chỉ chọn được chuỗi rỗng) thì in 0.
   • Ngược lại in dp[0].

Lưu ý / Pitfall

• Không thể dùng greedy đơn giản kiểu “xóa ít chữ số nhất” vì mục tiêu là giá trị lớn nhất, phụ thuộc vị trí chữ số (subsequence).
• Chuỗi rỗng chỉ dùng làm trạng thái gốc; nếu cuối cùng vẫn rỗng thì coi như không tạo được số hợp lệ.

Độ phức tạp

• Mỗi chữ số cập nhật 3 trạng thái, mỗi lần nối chuỗi có thể tốn \(O(L)\) với \(L\) là độ dài chuỗi hiện tại.
  • Trong Python, cách này thường vẫn AC với \(|N| \le 10^4\) do số trạng thái chỉ là 3, nhưng về mặt lý thuyết có thể lớn.
• Ước lượng theo code hiện tại:
  • Thời gian: khoảng \(O(3 \cdot |N| \cdot L)\) trong trường hợp xấu do nối chuỗi.
  • Bộ nhớ: \(O(L)\) cho các chuỗi trong dp.

(Trong thực tế bài này chấp nhận với cài đặt trên.)

Code tham khảo

def better(a, b):
    """Trả về chuỗi lớn hơn theo tiêu chí: dài hơn, hoặc cùng dài nhưng lớn hơn về từ điển"""
    if a is None:
        return b
    if b is None:
        return a
    if len(b) > len(a) or (len(b) == len(a) and b > a):
        return b
    return a

N = input().strip()
dp = ["", None, None]  # dp[0] = "", dp[1] = None, dp[2] = None

for ch in N:
    d = int(ch)
    new_dp = dp[:]  # sao chép (mặc định là không chọn ch)
    # Thêm chữ số vào các dãy con hiện có
    for r in range(3):
        if dp[r] is not None:
            new_r = (r + d) % 3
            new_dp[new_r] = better(new_dp[new_r], dp[r] + ch)
    # Bắt đầu chuỗi mới chỉ với ch
    new_dp[d % 3] = better(new_dp[d % 3], ch)
    dp = new_dp

ans = dp[0]
if ans == "":
    print(0)
else:
    print(ans)