GFSSOC '15 Winter S3 - PalinDrone - DMOJ: Modern Online Judge

GFSSOC '15 Winter S3 - PalinDrone

Points: 7 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem type

You've finished (or at least tried… hopefully) fixing up ButaneBot's OR-sum and Sokoban programs! Now you need to enter ButaneBot's files and update the code. There is a single problem now… to update the code you need to enter ButaneBot's security password, which Butane implemented to stop users from tampering with his files. ButaneBot cannot recall the password, but he remembers that it was a single integer under $10^N$ $10^{N}$ . He also remembers that the number is a palindrome. Before you begin coding a brute force check-all-palindromes program to hack into ButaneBot's files, you would like to know how many possible passwords there could be to make sure the program won't run on forever. Since this number may be very big, output the answer modulo $1\,000\,000\,000$ $1 000 000 000$ .

Input Specification

The only line of input will contain a single integer, $N$ $N$ $(1 \le N \le 10^{25})$ $(1 \leq N \leq 10^{25})$ .

You can assume that 80% of test cases will have $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ .

Output Specification

The number of palindromes under $10^N$ $10^{N}$ .

Sample Input

Copy

Sample Output

Copy

The palindromes less than or equal to $10^2$ $10^{2}$ are:

$\displaystyle 1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99$ $1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99$

Comments

3

JustinXu commented on Dec. 8, 2018, 7:16 p.m.

why am I WA'ing on test case 4

0

Overseas commented on Dec. 30, 2020, 11:25 a.m. ← edited →

I found the $N$ $N$ value to be $3849$ $3849$ for question 4, but still got no idea what is wrong with the answer

1

WilliamWu277 commented on Dec. 30, 2020, 4:14 p.m. ← edited →

"Since this number may be very big, output the answer modulo $1\,000\,000\,000$ $1 000 000 000$ ."

Also, your solution is too slow. For the later cases it will TLE.

0

Overseas commented on Dec. 30, 2020, 5:39 p.m.

Thank you for your response, by the way, this question really takes me hours to solve bc I didn't know it says "result = result% 1 Billion"

-3

Overseas commented on Dec. 30, 2020, 5:24 p.m.

bruh, i got 0.11s for my solution, check the list out

-8

Anix55 commented on Feb. 21, 2017, 1:24 p.m.

Zero isn't added into the palindrome count right?

This comment is hidden due to too much negative feedback. Show it anyway.

-4

susheelk commented on Feb. 22, 2017, 3:08 a.m.

I have the same question