Số đối xứng (Tin học trẻ toàn quốc 2025 – Vòng chung kết toàn quốc – Bảng B)
Đề bài
Một số được gọi là số đối xứng nếu đọc các chữ số của nó từ trái sang phải hay từ phải sang trái đều giống nhau. Ví dụ $7$, $99$, $121$, $1331$ là các số đối xứng, còn $123$ hay $10$ thì không.
Cho số tự nhiên $N$. Hỏi phải cộng thêm vào $N$ ít nhất bao nhiêu đơn vị để được một số đối xứng? (Nếu bản thân $N$ đã đối xứng thì đáp án là $0$.)
Dữ liệu vào: một dòng chứa số tự nhiên $N$, $N$ có không quá $16$ chữ số.
Kết quả: in ra một số tự nhiên – số đơn vị ít nhất cần cộng thêm.
Subtask:
- Subtask 1 ($80\%$ số điểm): $N$ có không quá $8$ chữ số.
- Subtask 2 ($20\%$ số điểm): $N$ có không quá $16$ chữ số.
Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.
12381210Giải thích: ví dụ 1: $123 + 8 = 131$ là số đối xứng nhỏ nhất không nhỏ hơn $123$. Ví dụ 2: $121$ đã là số đối xứng nên không cần cộng thêm gì.
Lời mở đầu
Bài mở màn của bảng B vòng chung kết. Cách "ngây thơ" – cứ cộng 1, cộng 1 rồi kiểm tra – đã ăn được 80% số điểm. Để lấy nốt 20% còn lại với $N$ tới 16 chữ số, ta cần một nhận xét nhỏ mà rất đẹp: số đối xứng được quyết định hoàn toàn bởi nửa đầu của nó. Mình sẽ đi lần lượt hai cách, cả hai đều chạy thật trên bộ test để các bạn thấy rõ mỗi cách được bao nhiêu điểm.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test có gì?
Bộ test trên CLUE gồm 25 test do mình tự sinh theo đúng tỉ lệ subtask của đề (test 1, 2 là hai ví dụ của đề):
| Nhóm | Test | Số chữ số của $N$ | Số test đáp án 0 | Đáp án lớn nhất |
|---|---|---|---|---|
| Subtask 1 (80%) | 1–20 | 1, 2, 3, 4, 5, 7, 8 | 5 | 10.999 (test 20) |
| Subtask 2 (20%) | 21–25 | 16 | 1 | 98.888.889 (test 23) |
- Có đủ các trường hợp "bẫy": $N = 0$, $N$ có 1 chữ số, $N$ đã đối xứng sẵn (đáp án 0), $N = 10^k$ (đáp án 1, ví dụ $1000 + 1 = 1001$), $N$ toàn chữ số 9, và trường hợp nửa đầu phải tăng thêm 1 có nhớ (như $1\,299\,999 \to 1\,300\,031$).
- Ở subtask 1, đáp án lớn nhất chỉ cỡ $10^4$; nhưng ở subtask 2 ($N$ có 16 chữ số) đáp án có thể lên tới gần $10^8$ – đây là chỗ phân biệt cách "thử từng số" với cách "lật gương".
Kết quả chạy thật của từng cách trên từng subtask (C++):
| Subtask | Điều kiện | Test | Cách 1 thử từng số | Cách 2 lật gương |
|---|---|---|---|---|
| Subtask 1 (80%) | $N$ có không quá 8 chữ số | 1–20 | qua | qua |
| Subtask 2 (20%) | $N$ có không quá 16 chữ số | 21–25 | 3/5 test | qua |
Lời giải cách 2 (C++) mình đã nộp thử trên hệ thống chấm chính thức của hội thi (tinhoctre.vn) và đạt AC 100/100 điểm.
Ý tưởngNửa đầu quyết định tất cả
Gọi $L$ là số chữ số của $N$ và $h = \lceil L/2 \rceil$. Một số đối xứng có $L$ chữ số chỉ cần biết $h$ chữ số đầu (gọi là nửa đầu) là dựng lại được cả số: nửa sau chính là nửa đầu viết ngược (nếu $L$ lẻ thì chữ số giữa không lặp lại). Ví dụ nửa đầu 12 với $L = 3$ cho $121$, với $L = 4$ cho $1221$. Ta gọi thao tác này là lật gương.
Hơn nữa, hai số đối xứng cùng $L$ chữ số thì số nào có nửa đầu lớn hơn sẽ lớn hơn (vì so sánh hai số cùng độ dài là so từ chữ số đầu tiên). Từ đó:
- Lấy nửa đầu của chính $N$ rồi lật gương được số đối xứng $p$. Mọi số đối xứng có nửa đầu nhỏ hơn thì đều nhỏ hơn $N$ (vì $h$ chữ số đầu đã nhỏ hơn). Vậy nếu $p \ge N$ thì $p$ chính là số đối xứng nhỏ nhất $\ge N$.
- Nếu $p < N$: tăng nửa đầu thêm $1$ rồi lật gương lại. Số mới có nửa đầu lớn hơn nửa đầu của $N$ nên chắc chắn $> N$, và nó là số đối xứng kế tiếp sau $p$.
Em nhập $N$ rồi bấm Tiếp để xem từng bước lật gương:
Cách 1Thử cộng từng đơn vị
Cách tự nhiên nhất: thử $d = 0, 1, 2, \ldots$ và dừng ở giá trị $d$ đầu tiên mà $N + d$ là số đối xứng. Để kiểm tra một số $x$ có đối xứng không, ta lật ngược các chữ số của $x$ (lấy dần chữ số cuối bằng % 10, bỏ chữ số cuối bằng / 10) được số $y$, rồi so sánh $y$ với $x$.
- Dòng
y = y * 10 + t % 10đẩy các chữ số cũ của $y$ sang trái một bậc rồi gắn chữ số cuối của $t$ vào – sau vòng lặp $y$ là $x$ viết ngược. - Vòng
whiletrongmainchắc chắn dừng vì số $99\ldots9$ luôn là số đối xứng. - Với $N = 0$: hàm trả về
y == xlà0 == 0, đúng – đáp án 0.
Kết quả chạy thật: bản C++ đúng 23/25 test – quá thời gian test 23, 25 (test đúng chạy lâu nhất 0,004 giây). Bản Python đúng 23/25 test – quá thời gian test 23, 25 (test đúng chạy lâu nhất 0,019 giây).
Với $N$ tối đa 8 chữ số, khoảng cách tới số đối xứng gần nhất chỉ cỡ $10^4$ nên chạy tức thì. Nhưng khi $N$ có 16 chữ số, khoảng cách có thể gần $10^8$ (ví dụ $N = 1234567898765432$ phải cộng tới $98\,888\,889$), nhân thêm 16 phép chia cho mỗi lần kiểm tra là quá 1 giây.
Cách 2Lật gương nửa đầu – O(L)
Cài đặt đúng như phần ý tưởng. Mình đọc $N$ vào một xâu để tiện cắt nửa đầu, hàm latGuong(nua, L) ghép nửa đầu với phần đảo ngược của nó (bỏ chữ số giữa nếu $L$ lẻ: chỉ lấy $\lfloor L/2 \rfloor$ chữ số đầu của nua để đảo).
s = to_string(n): phòng khi dữ liệu có số 0 ở đầu (như007) thì độ dài $L$ vẫn tính đúng theo giá trị thật của $N$.- Vòng
for(int i = L / 2 - 1; i >= 0; i--)chép ngược $\lfloor L/2 \rfloor$ chữ số đầu: $L = 3$,nua = "12"→ chỉ chépnua[0]→"121"; $L = 4$ → chépnua[1], nua[0]→"1221". - $N < 10^{16}$ nên mọi số đều vừa kiểu
long long.
Kết quả chạy thật: bản C++ đúng 25/25 test, chậm nhất 0,004 giây. Bản Python đúng 25/25 test, chậm nhất 0,023 giây.
Nhận xét
Đăng nhận xét