(ACM/ICPC 2020) Đếm số Palindrome

Đề bài:
Số palindromic là một số giống nhau khi viết về phía xuôi hoặc
ngược. Do đó, một vài số palindromic đầu tiên là 1, 2, 3, 4, 5, 6, 7, 8, 9, 11,
22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, … (quy tắc 1).
Trong một số trường hợp đặc biệt, 0012100, 00 là một số palindromic. Do đó, 12100, 1210, 00
cũng là một số palindromic (quy tắc 2).

Chúng ta có thể phân loại số nguyên dương thành ba loại:
Loại 0: các số không phải số palindromic.
Loại 1: số palindromic theo quy tắc 1.
Loại 2: số palindromic theo quy tắc 2.

Tất cả các palindrome nhỏ hơn hoặc bằng 100 là: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 20, 22, 30,
33, 40, 44, 50, 55, 60, 66, 70, 77, 80, 88, 90, 99, 100.

Cho số M là số nguyên không âm. Hàm F (M) trả về số
palindromes (gồm 2 loại: loại 1 và loại 2) nhỏ hơn hoặc bằng M (0 ≤ M ≤ 10^35).

M 0 15 39 55 60 85 88 90 100
F(M) 1 12 16 20 21 25 26 27 29

Để đơn giản hóa vấn đề, cho trước một số N là số nguyên không âm, hàm P (N) trả về

giá trị của F (10^N) (0 ≤ N ≤ 35).
N 0 1 2 3 4 … 15 … 35
P(N) 2 11 29 137 335 … 144,444,413 … 1,444,444,444,444,444,373

Đầu vào: Trên dòng đầu tiên là số lượng test, 1 ≤ T ≤ 36.
Trong T dòng tiếp theo, mỗi dòng chứa một số nguyên Ni không âm (1 ≤ Ni ≤ T, 0 ≤ Ni ≤ 35).
Đầu ra: Kết quả có T dòng, dòng thứ i ghi giá trị của P (Ni) (1 ≤ i ≤ T).
Ví dụ:

input:
5
4
7
35
20
15
output:
335
14429
1444444444444444373
34444444403
144444413

input:
3
1
8
10
output:
11
34427
344423

input:
5
30
2
3
33
25
output:
3444444444444383
29
137
144444444444444377
14444444444393

Bạn chưa đăng nhập? Đăng nhập để Submit ngay!