Tóm tắt đề bài

Cho hai số tự nhiên \(A\) và \(B\) (dưới dạng chuỗi). Có vô hạn “mảnh giấy” ghi đúng số \(A\) hoặc đúng số \(B\). Hãy ghép một số lượng hữu hạn các mảnh theo thứ tự từ trái sang phải để tạo thành một số:

• Chia hết cho \(9\).
• Mỗi loại \(A\) và \(B\) phải xuất hiện ít nhất một lần.
• Số tạo thành là nhỏ nhất có thể.

Phân tích

• Tính chia hết cho \(9\) phụ thuộc vào tổng chữ số của toàn bộ số.
  • Một số chia hết cho \(9\) khi và chỉ khi tổng chữ số chia hết cho \(9\).
• Khi ghép các “khối” \(A\), \(B\) (mỗi khối là một chuỗi chữ số), tổng chữ số của kết quả bằng:

trong đó \(i, j \ge 1\) là số lần dùng \(A\), \(B\); \(s(X)\) là tổng chữ số của \(X\).

• Tuy nhiên, code AC không tính trực tiếp \(s(A), s(B)\) mà dựa trên nhận xét: chỉ cần thử số lần lặp rất nhỏ (tối đa \(9\)) là đủ để tìm được bội của \(9\) do tính chất theo modulo \(9\).
• Mục tiêu “nhỏ nhất”:
  • Số có ít chữ số hơn thường nhỏ hơn.
  • Nếu cùng độ dài thì so sánh từ trái qua phải (so sánh chuỗi/so sánh số).

Code AC chọn cách xây dựng số theo dạng:

• Nếu không có trường hợp đặc biệt: tạo số là A lặp \(i\) lần nối với B lặp \(j\) lần (tức là \(A^iB^j\) theo nghĩa ghép chuỗi).
• Đặc biệt khi một trong hai là "0": tránh để số bắt đầu bằng 0 và xử lý riêng.

Hướng giải quyết

Nhận xét chính

1. Chỉ cần thử \(i, j\) trong đoạn \(1..9\):
   • Xét modulo \(9\), giá trị \(i \cdot s(A) + j \cdot s(B)\) chỉ có \(9\) trạng thái.
   • Khi tăng \(i\) hoặc \(j\), phần dư modulo \(9\) lặp lại theo chu kỳ \(9\).
   • Vì vậy, nếu tồn tại nghiệm với \(i, j \ge 1\) thì sẽ có nghiệm với \(1 \le i, j \le 9\) (tinh thần là “quét đủ một chu kỳ”).
2. Để số ghép nhỏ nhất, code AC:
   • Đảm bảo \(a \le b\) theo so sánh chuỗi (lexicographic) bằng cách nếu a > b thì hoán đổi.
   • Sau đó xét các ứng viên dạng a*i + b*j (ghép chuỗi) và lấy nhỏ nhất thỏa chia hết cho \(9\).
3. Trường hợp \(a = "0"\):
   • Nếu để 0 đứng đầu sẽ tạo số có nhiều chữ số hơn nhưng giá trị lại bị “mất” các số 0 đầu (không hợp lý khi biểu diễn số).
   • Code cố định dạng: b + a + b*(i-1) tức là b 0 b...b để đảm bảo chữ số đầu tiên không phải 0, đồng thời vẫn dùng đủ cả hai loại.

Thuật toán (theo code AC)

1. Đọc hai chuỗi a, b. Nếu a > b thì hoán đổi để a “nhỏ hơn”.
2. Nếu a == "0":
   1. Với \(i\) từ \(1\) đến \(9\):
      • Tạo chuỗi s = b + a + b*(i-1).
      • Đổi sang số nguyên c = int(s) và kiểm tra c % 9 == 0.
      • In c tại nghiệm đầu tiên (do tăng dần \(i\) nên sẽ cho kết quả nhỏ nhất theo cách xây dựng này).
3. Ngược lại (a != "0"):
   1. Khởi tạo ans là một số rất lớn.
   2. Với \(i\) từ \(1\) đến \(9\):
      • Với \(j\) từ \(1\) đến \(9\):
        • Tạo chuỗi s = a*i + b*j, đổi sang c = int(s).
        • Nếu c % 9 == 0 và c < ans thì cập nhật ans.
   3. In ans.

Lưu ý / “pitfall”

• So sánh a > b trong Python là so sánh từ điển (lexicographic), không phải so sánh theo giá trị số. Code AC dựa trên tiêu chí này để “ưu tiên khối nhỏ hơn đứng trước”, và sau đó brute force số lần lặp nhỏ để chọn min thực sự.
• Chuyển chuỗi rất dài sang int có thể tạo số nguyên lớn, nhưng Python hỗ trợ big integer. Code AC cũng giới hạn số lần lặp \(\le 9\) nên độ dài vẫn trong tầm kiểm soát với ràng buộc đề (các subtask cho thấy \(A,B\) không quá lớn).

Độ phức tạp

• Trường hợp thường: thử tối đa \(9 \cdot 9 = 81\) ứng viên.
• Thời gian: \(O(81 \cdot L)\) với \(L\) là độ dài chuỗi ghép (do tạo chuỗi và chuyển int), về thực tế là hằng số nhỏ.
• Bộ nhớ: \(O(L)\) cho chuỗi/biến tạm.

Code tham khảo

a = input()
b = input()

# Đảm bảo a "không lớn hơn" b theo so sánh chuỗi (lexicographic)
if a > b:
    a, b = b, a

# Trường hợp đặc biệt: a = "0" để tránh số bắt đầu bằng 0
if a == "0":
    for i in range(1, 10):
        # Dạng: b + 0 + b*(i-1)  => luôn bắt đầu bằng b (khác 0)
        c = int(b + a + b * (i - 1))
        if c % 9 == 0:
            print(c)
            break
else:
    ans = 10 ** 100  # số đủ lớn
    for i in range(1, 10):
        for j in range(1, 10):
            # Ghép i lần a rồi j lần b
            c = int(a * i + b * j)
            if c % 9 == 0 and ans > c:
                ans = c
    print(ans)