Palindrome Numbers

http://acm.pku.edu.cn/JudgeOnline/problem?id=2402

Description

A palindrome is a word, number, or phrase that reads the same forwards as backwards. For example, the name "anna" is a palindrome. Numbers can also be palindromes (e.g. 151 or 753357). Additionally numbers can of course be ordered in size. The first few palindrome
numbers are: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, ...
The number 10 is not a palindrome (even though you could write it as 010) but a zero as leading digit is not allowed.

Input

The input consists of a series of lines with each line containing one integer value i (1<= i <= 2*10^9 ). This integer value i indicates the index of the palindrome number that is to be written to the output, where index 1 stands for the first palindrome number (1), index 2 stands for the second palindrome number (2) and so on. The input is terminated by a line containing 0.

Output

For each line of input (except the last one) exactly one line of output containing a single (decimal) integer value is to be produced. For each input value i the i-th palindrome number is to be written to the output.

Source

Tehran 2003 Preliminary


Solving

앞에서 읽을 때과 뒤에서 읽을 때 똑같이 읽어지는 것을 Palindrome이라 한다. n이 주어졌을 때 n번째 Palindrome number를 구하라.

우선 10보다 작은 9개의 숫자는 Palindrome이다. 10~99 사이의 숫자 중 Palindrome은 11, 22, 33, 44, 55, 66 77, 88, 99 9개가 있다. 세자리의 숫자 중 Palindrome은 101, 111, 121, 131, ... 202, 203, 204, ... , 989, 999 가 있다.

법칙을 발견하기 어렵지만 이 숫자를 반으로 나눠보면 조금은 알기 쉬워진다.
한자리의 숫자는 1, 2, 3, 4, 5, 6, 7, 8, 9 가 있다. (9개)
두자리의 숫자는 1, 2, 3, 4, 5, 6, 7, 8, 9 가 반복해서 나온다. (9개)
세자리의 숫자는 10, 11, 12, 13, ..., 20, 21, 22, ... , 97, 98, 99 에 가장 앞자리 수를 덧붙인 숫자가 있다. (90개)
네자리의 숫자는 10, 11, 12, 13, ..., 20, 21, 22, ... , 97, 98, 99 에 이 숫자를 반대로해서 덧붙은 숫자가 있다. (90개)
다섯자리 숫자는 100, 101, 102, 103 , ..., 999 ......... (900개)
...
이런식의 법칙을 발견하게 된다.

자리수가 두자리씩 올라갈때 그 자리숫자에 존자하는 Palindrome은 10배씩 증가하게 된다.

이 법칙을 잘 정리하여 코딩하면 되겠다.

#include <cstdio> #include <cstdlib> int main() { int n; long long l, m, x, r; int i; char buffer[100]; while (scanf("%d", &n) > 0) { if (n == 0) break; l = 0; m = 0; x = 1; while (n > m) { r = m; m += 18*x; x *= 10; l++; } n -= r; sprintf(buffer, "%d", (int)(n <= (m-r)/2 ? n+x/10-1 : n-(m-r)/2+x/10-1)); for (i = 0; i < l; i++) printf("%c", buffer[i]); if (n > (m-r)/2) i = l-1; else i = l-2; for (;i >= 0; i--) printf("%c", buffer[i]); printf("\n"); } return 0; }