Tóm tắt đề bài

“Số chẵn tròn” là số chẵn mà khi viết ngược lại vẫn là số chẵn. Với một số tự nhiên \(N\) (\(N \le 10^9\)), hãy đếm số lượng số chẵn tròn nhỏ hơn \(N\).

Phân tích

Một số là chẵn khi và chỉ khi chữ số tận cùng là chẵn. Số đảo của nó là chẵn khi và chỉ khi chữ số đầu tiên của số ban đầu là chẵn.

Vì vậy, một số \(x\) là “chẵn tròn” khi và chỉ khi:

• Chữ số đầu (most significant digit) của \(x\) là chẵn: thuộc \(\{2,4,6,8\}\).
• Chữ số cuối (least significant digit) của \(x\) là chẵn: thuộc \(\{0,2,4,6,8\}\).
• Và \(x\) là số có độ dài \(l \ge 1\) (không xét số có chữ số đầu là \(0\)).

Bài toán trở thành: đếm các số \(x < N\) sao cho chữ số đầu chẵn và chữ số cuối chẵn.

Nhận xét theo độ dài:

• Với \(l = 1\): các số thỏa là \(2,4,6,8\) ⇒ có \(4\) số.
• Với \(l \ge 2\):
  • Chữ số đầu có \(4\) cách: \(\{2,4,6,8\}\)
  • Chữ số cuối có \(5\) cách: \(\{0,2,4,6,8\}\)
  • \(l-2\) chữ số giữa tự do: \(10^{l-2}\) cách
    ⇒ tổng \(4 \cdot 5 \cdot 10^{l-2}\) số.

Do \(N \le 10^9\) nên \(l \le 10\), có thể đếm theo chữ số rất nhanh.

Hướng giải quyết

Ý tưởng chính

Đếm số chẵn tròn nhỏ hơn \(N\) theo 2 phần:

1. Đếm tất cả số chẵn tròn có độ dài nhỏ hơn \(l = \text{len}(N)\).
2. Đếm số chẵn tròn có đúng độ dài \(l\) nhưng nhỏ hơn \(N\).

AC code đang làm đúng theo hai bước đó.

Bước 1: Đếm theo độ dài nhỏ hơn \(l\)

Duyệt \(i = 1 \ldots l-1\):

• Nếu \(i = 1\): cộng \(4\).
• Nếu \(i \ge 2\): cộng \(4 \cdot 5 \cdot 10^{i-2}\).

Bước 2: Đếm các số có độ dài \(l\) và nhỏ hơn \(N\)

Gọi \(t\) là chữ số đầu của \(N\).

2.1. Chọn chữ số đầu nhỏ hơn \(t\)

Với mỗi chữ số đầu \(d\) thỏa \(1 \le d < t\) và \(d\) chẵn (tức \(d \in \{2,4,6,8\}\), đồng thời \(d < t\)):

• Với mỗi \(d\), số lượng cách chọn phần còn lại (từ chữ số thứ 2 đến chữ số cuối) sao cho chữ số cuối chẵn là:

  • Có \(10^{l-2}\) cách chọn \(l-2\) chữ số giữa
  • Có \(5\) cách chọn chữ số cuối chẵn

⇒ cộng thêm \(10^{l-2} \cdot 5\).

Trong code:

• Duyệt i in range(1, t) và nếu i % 2 == 0 thì cộng (10 ** (l - 2)) * 5.

2.2. Trường hợp chữ số đầu bằng \(t\) (chỉ khi \(t\) chẵn)

Nếu \(t\) lẻ thì không thể tạo số chẵn tròn có cùng chữ số đầu, dừng tại đây.

Nếu \(t\) chẵn, ta cần đếm các số dạng:

• Chữ số đầu cố định là \(t\)
• Phần còn lại là một số \(x\) có đúng \(l-1\) chữ số (cho phép có số 0 ở đầu phần này), sao cho tổng số tạo ra \(< N\) và chữ số cuối chẵn.

Gọi:

Khi đó \(\text{tmp}\) chính là giá trị của \(l-1\) chữ số còn lại của \(N\).

Ta cần đếm số \(x\) thỏa \(0 \le x < \text{tmp}\) và chữ số cuối chẵn.
Trong dãy các số từ \(0\) đến \(\text{tmp}\) (tính cả \(\text{tmp}\) để dễ công thức), cứ 2 số liên tiếp thì có đúng 1 số chẵn, nên số lượng số chẵn trong đoạn \([0, \text{tmp}]\) là:

Trong code dùng:

• answer += (tmp + 1) // 2

Lưu ý: vì bài yêu cầu nhỏ hơn \(N\), việc cộng số chẵn trong \([0, \text{tmp}]\) tương ứng với các số có hậu tố \(\le \text{tmp}\), tức là các số \(\le N\) với chữ số đầu \(t\). Nhưng do \(N\) tự nó có thể không thỏa “chẵn tròn” (thường là vậy), cách đếm này vẫn phù hợp với logic của code: đang đếm số hậu tố tạo ra số không vượt quá \(N\) trong nhánh chữ số đầu bằng \(t\), và kết quả khớp do điều kiện chẵn ở chữ số cuối đã được “lọc” bằng phép chia 2. (Nếu muốn tuyệt đối chặt theo “< N”, có thể diễn giải rằng ta đang đếm số chẵn \(x\) trong \([0, \text{tmp}-1]\), và công thức tương đương tùy theo \(\text{tmp}\) chẵn/lẻ; code đã xử lý đúng với bài gốc.)

Các lỗi hay gặp

• Nhầm điều kiện “đảo vẫn chẵn” thành phụ thuộc chữ số cuối, trong khi thực ra phụ thuộc chữ số đầu của số ban đầu.
• Quên trường hợp \(l=1\) (không có phần “giữa”).
• Đếm nhầm “< N” và “\(\le N\)” khi xử lý theo tiền tố/hậu tố.

Độ phức tạp

• Thời gian: \(O(l)\) với \(l = \text{len}(N) \le 10\).
• Bộ nhớ: \(O(1)\).

Code tham khảo

# AC solution (PyPy3) - đếm số "chẵn tròn" nhỏ hơn N
n = input()
l = len(n)
answer = 0

# 1) Đếm các số có độ dài nhỏ hơn l
for i in range(1, l):
    if i == 1:
        answer += 4
    else:
        answer += 4 * 5 * (10 ** (i - 2))

# 2) Đếm các số có độ dài đúng l nhưng < N theo chữ số đầu
t = int(n[0])

# 2.1) Chữ số đầu nhỏ hơn t và chẵn
for i in range(1, t):
    if i % 2 == 0:
        answer += (10 ** (l - 2)) * 5

# 2.2) Chữ số đầu bằng t (chỉ khi t chẵn)
if t % 2 == 0:
    n = int(n)
    tmp = n - (10 ** (l - 1)) * t  # phần còn lại sau khi bỏ chữ số đầu
    answer += (tmp + 1) // 2       # đếm số hậu tố có chữ số cuối chẵn

print(answer)