(ACM / ICPC 2020) Count the Palindromes

Threads:
Số palindromic là một số giống nhau khi viết về phía xuôi hoặc
ngược. Therefore, The first few palindromic numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, 11,
22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, … (Rule 1).
Trong một số trường hợp đặc biệt, 0012100, 00 là một số palindromic. Therefore, 12100, 1210, 00
cũng là một số palindromic (Rule 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 to be: 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

Input: 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).
Output: Kết quả có T dòng, dòng thứ i ghi giá trị của P (Ni) (1 ≤ i ≤ T).
For example:

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

You are not logged in? Log in to Submit Now!