PALIN - 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


hide comments
meonspoj01: 2019-09-29 20:08:18

"For a given positive integer K of not more than 1000000 digits", really 1000000 digits or it talks about the input being less than it?

aemie_305: 2019-09-12 19:06:51

Last edit: 2019-09-12 19:12:15
pretam9: 2019-08-26 16:20:25

The question was damn good....took me 3 hrs to understand and implement

kmkhan_014: 2019-08-16 13:12:56

ye question hatao, har company yehi puchti hai

Last edit: 2019-08-24 12:59:57
mriow: 2019-08-13 09:35:32

It works fine with python3, BUT do not convert ever from string to int (do not use int() on python) since it is a HUGE slow down of the running time, giving even a TLE error.
(the slow down is also true regardless of the language)

Last edit: 2019-08-13 09:36:03
thirumalai: 2019-08-13 08:39:36

Does this work in python?

hit7sh: 2019-08-09 17:48:01

Works perfectly in Bluej and shows compilation error in here. Like wtf!?

bnnj: 2019-08-05 12:49:50

I think there might be something wrong with this problem / its judge.
Here's what i did:
I made a checker program to test the output of the palindrome program, it verifies if it's a valid palindrome, if it's bigger than the input, and if there are no palindrome bigger than input and smaller than output.
then i tested it with that (after modifying palin to output the input as well, so that checker knows what it's dealing with):
ruby -e "puts (100000001); puts (0..100000000).to_a" | ./palin | ./checker 2> log_errors.txt
which tests every number from 0 to 100,000,000.
Found no issue.
i then made a generator of random numbers strings of random length up to 1,000,000,000 digits, and ran
./gen | ./palin | ./checker
after running for more than 3 hours, several times, i found no case where the output was wrong.
So i thought maybe the checker was wrong, and tested the checker. It does tell me properly when the output is wrong, but to make sure i searched the internet for a source code for a palindrome program that does passes the judge. I submitted it myself to make sure it passed. I called this program "ref"
Then i ran the tests again:
ruby -e "puts (100000001); puts (0..100000000).to_a" | ./ref > ref_output
ruby -e "puts (100000001); puts (0..100000000).to_a" | ./palin > my_output
diff ref_output my_output
No difference at all.
I generated a test file of 10,000,000 random test cases with the generator, added some edge cases, then ran
cat test_file | ./ref > ref_output
cat test_file | ./palin > my_output
diff ref_output my_output
No difference.

Is there something wrong in my tests ? Is there something i don't understand about the input ?
Here are my files :
https://github.com/BNNJ/SPOJ/tree/master/PALIN

Last edit: 2019-08-05 12:52:05
bnnj: 2019-08-01 16:35:34

Hi,
inputing 09 in the toolkit tester (http://spojtoolkit.com/test/PALIN) gives 0 as the answer.
I don't get it, shouldn't it be 11 ?

naman_mawandia: 2019-07-13 08:27:17

1->2


Added by:adrian
Date:2004-05-01
Time limit:2s-9s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6

Problem's scores 1 vote

Concept difficulty
Concept difficulty 37%
Implementation difficulty
Implementation difficulty 50%
456 15