**Nhận xét:** Nếu một số $x$ có $m$ chữ số là cân bằng, thì tồn tại duy nhất một $1 \le p \le m$ sao
cho hai vế trái phải bằng nhau.
Việc chứng minh khá đơn giản: Nếu gọi $L_p$ và $R_p$ lần lượt là hai biểu thức tổng trái và phải
ứng với $p$, thì $L$ tăng ngặt và $R$ không tăng khi $p$ đi từ trái sang phải, nên hai dãy chỉ có
thể giao nhau tại nhiều nhất một điểm.
Thế để tính số lượng số cân bằng từ $1$ đến $n$, ta chỉ cần cố định từng $p$, từ đó điều kiện cân
bằng dễ xử lý hơn nhiều. Cụ thể, hàm đệ quy để đếm sẽ lưu các thông tin sau:
+ $i$: đang xét chữ số thứ $i$ từ lớn về nhỏ;
+ $\texttt{tight}$: tiền tố $i$ chữ số đầu tiên của số đang dựng này có khớp với $n$ hay không;
+ $\texttt{pos}$: kể từ chữ số khác $0$ đầu tiên của số đang dựng, ta đang xét chữ số thứ $\texttt{pos}$;
+ $S$: tổng đóng góp của các chữ số từ $1$ đến $\texttt{pos}$.
Trong đó, đóng góp vào $S$ của chữ số $x$ tại vị trí thứ $\texttt{pos}$ kể từ chữ số khác $0$ đầu tiên là:
+ $x \times (p - \texttt{pos})$ nếu $\texttt{pos} < p$;
+ $0$ nếu $\texttt{pos} = p$;
+ $-[x \times (\texttt{pos} - p)]$ nếu $\texttt{pos} > p$.
Điều kiện cơ sở của số thỏa mãn là khi $\texttt{pos} \ge p$ và $S = 0$. Để ý là ta đặt các phép trừ
ở phía sau trong khi đệ quy, nên khi $S<0$ thì ta có thể thoát ngay.
Hơn nữa, giá trị lớn nhất của $S$ đạt được trong khi đệ quy với số có chữ số $9$ lặp lại $17$ lần:
tại $p=9$, tổng bên trái bằng $9 \times (1 + 2 + \dots + 8) = 324$. Vậy nên số trạng thái của hàm
đệ quy là $18 \times 2 \times 18 \times 324 = 209952$, hoàn toàn đủ nhanh.
tuongll
Created at
0 likes