coreBugZJ

此 blog 已弃。

PALIN - SPOJ 5. The Next Palindrome

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222

Warning: large Input/Output data, be careful with certain languages


问题：
求出比输入整数大的最小的回文数，输入整数不超过 1000000 个数字。

解法：
贪心。

代码 LISP SBCL ：
 1(defun digit-succ(x)
 2 (elt "0123456789A" (position x "*0123456789")))
 3
 4(let ((num (read)))
 5 (dotimes (ca num)
 6  (let* ((str (read-line))
 7         (len (length str))
 8         (cmp 0)
 9         (i nil)
10         (j nil))
11   (dotimes (i (floor (/ (1+ len) 2)))
12    (setf j (1- (- len i)))
13    (when (char> (elt str i) (elt str j))
14     (setf cmp 1))
15    (when (char< (elt str i) (elt str j))
16     (setf cmp -1))
17    (setf (elt str j) (elt str i)))
18   (when (<= cmp 0)
19    (setf i (1- (floor (/ (1+ len) 2))))
20    (setf j (if (oddp len) i (1+ i)))
21    (do ()
22     ((or (minusp i) (char< (elt str i) #\9)))
23     (setf (elt str i) #\0)
24     (setf (elt str j) #\0)
25     (decf i)
26     (incf j))
27    (when (minusp i)
28     (setf (elt str 0) #\1)
29     (write-string str)
30     (write-char #\1))
31    (when (not (minusp i))
32     (setf (elt str i) (digit-succ (elt str i)))
33     (setf (elt str j) (elt str i))
34     (write-string str)))
35   (when (plusp cmp)
36    (write-string str))
37   (fresh-line))))
38
39


posted on 2012-02-19 16:18 coreBugZJ 阅读(382) 评论(0)  编辑 收藏 引用 所属分类: ACM 、Algorithm 、Lisp


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理