Đối xứng

Nguồn: CLUE OJ – Chương 19: Đệ quy cơ bản Độ khó: Dễ Đệ quy Số đối xứng

Đề bài

Bạn được cho một số nguyên dương $N$. Hãy kiểm tra số $N$ đó có phải là một số đối xứng hay không. Một số được gọi là đối xứng nếu như ta gọi $M$ là số được viết từ số $N$ nhưng viết các chữ số theo thứ tự ngược lại, thì ta được $N = M$.

Ví dụ $N = 12321$ được gọi là một số đối xứng, vì nếu ta lấy số $M$ là số được tạo thành bởi việc viết các chữ số trong số $N$ nhưng theo thứ tự ngược lại, ta vẫn được $M = 12321$.

Số $N = 102$ không được gọi là số đối xứng, vì $M = 201$ khác với $102$.

Dữ liệu nhập: gồm một số nguyên dương duy nhất là số $N$ $(1 \le N \le 1000000)$.

Dữ liệu xuất: gồm một chuỗi duy nhất là YES hay NO. Chuỗi là YES nếu như $N$ là số đối xứng và NO trong trường hợp ngược lại.

Ví dụ 1 – input

12321

Ví dụ 1 – output

YES

Ví dụ 2 – input

102

Ví dụ 2 – output

NO

Lời mở đầu

Kiểm tra số đối xứng thì các bạn đã làm bằng vòng lặp từ hồi học vòng while. Trong chương Đệ quy cơ bản, mình làm lại bài này theo 2 kiểu đệ quy rất hay gặp: đệ quy có tham số "tích luỹ" (lật số) và đệ quy co hai đầu trên xâu.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởngcây đệ quyCách 1lật sốCách 2co hai đầu

Bộ testBộ test chính thức có gì?

Số chữ số của N	2	3	4	5	6	Tổng
Số test	16	28	13	33	10	100
Trong đó YES	8	19	2	22	0	51

• 100 test, $N$ từ 11 đến 987.550 (không có số 1 chữ số; không có test $N = 10^6$). Có 51 test đáp án YES và 49 test NO; các test 53–100 đều là số đối xứng.
• Không chia subtask: $N$ có tối đa 7 chữ số nên mọi cách làm đều chỉ tốn vài phép tính – độ sâu đệ quy không quá 8 tầng.
• Số lật của $N$ không vượt quá $9.999.999$, vẫn nằm gọn trong int.

Ý tưởngHai cách nghĩ đệ quy

Cách 1 – lật số bằng đệ quy

dao(n, m): $n$ là phần chưa lật, $m$ là phần đã lật. Mỗi lần gọi, chuyển chữ số cuối của $n$ (là n % 10) sang cuối $m$: dao(n / 10, m * 10 + n % 10). Khi $n = 0$ thì $m$ chính là số lật. Ví dụ: dao(102, 0) → dao(10, 2) → dao(1, 20) → dao(0, 201) = 201 ≠ 102 → NO.

Cách 2 – co hai đầu xâu

Đọc $N$ thành xâu $s$. Đoạn s[l..r] đối xứng khi và chỉ khi s[l] == s[r] và đoạn bên trong s[l+1..r-1] đối xứng. Điểm dừng: đoạn còn 0 hoặc 1 ký tự ($l \ge r$) thì chắc chắn đối xứng.

Em chọn cách, nhập $N$ rồi bấm Tiếp để xem cây đệ quy:

Cách (1 hoặc 2): N =

Ví dụ nhanh:

Cách 1Đệ quy lật số

C++▶ Chạy tay từng dòng codeCách 1: dao(n, m) chuyển dần chữ số cuối của n sang m, so sánh số lật với N.

Dữ liệu vào (stdin) – sửa thoải mái12321

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đây là đệ quy đuôi: lời gọi đệ quy là việc cuối cùng của hàm, kết quả ở điểm dừng được "chuyền" nguyên vẹn về main.
2. Tham số m đóng vai trò biến tích luỹ – giống biến m = m * 10 + n % 10 trong vòng while quen thuộc, chỉ khác là mỗi vòng lặp giờ là một lời gọi hàm.
3. Lời gọi đầu tiên phải là dao(n, 0) – lúc đầu chưa lật được chữ số nào.

Không gian$O(\log_{10} N)$ (ngăn xếp)

Thời gian$O(\log_{10} N)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.005s; bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.035s.

Cách 2Đệ quy co hai đầu xâu

C++▶ Chạy tay từng dòng codeCách 2: doiXung(l, r) so 2 đầu xâu rồi co vào trong.

Dữ liệu vào (stdin) – sửa thoải mái12321

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Đọc $N$ thẳng vào string s (vì $N$ không có số 0 ở đầu nên xâu chính là cách viết của số).
2. Gặp một cặp khác nhau là return false ngay, không cần xét phần bên trong. Ví dụ 102: s[0] = '1' ≠ s[2] = '2' → NO chỉ sau 1 lời gọi.
3. Mỗi lời gọi co mỗi đầu vào 1 ký tự, nên số lời gọi khoảng (số chữ số) / 2.

Không gian$O(\log_{10} N)$

Thời gian$O(\log_{10} N)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.003s; bản Python đúng 100/100 test, test đúng chạy lâu nhất 0.026s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
1. Lật số	C++	100/100	0.005s	Full điểm
	Python	100/100	0.035s	Full điểm
2. Co hai đầu xâu	C++	100/100	0.003s	Full điểm
	Python	100/100	0.026s	Full điểm

Ghi chú của mình: cả 2 cách, C++ lẫn Python, đều đạt full điểm, mỗi test dưới 0,05 giây. Kiểu "co hai đầu" f(l, r) → f(l + 1, r - 1) của Cách 2 sẽ còn gặp lại nhiều ở các bài đảo ngược mảng, kiểm tra xâu đối xứng bằng đệ quy ở những bài sau.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇