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
chuang: 2020-05-31 11:27:28

My answers are right, but the time exceeds. Is it because I am using c# or my algorithm is not good enough...

yolo129: 2020-05-29 23:28:18

Check for 11, 111,... if you're getting WA even when every other case (in the comments) works!

shubham_0025: 2020-05-27 17:44:20

I am getting all correct answer, I need more test cases can anyone help?
One more thing to ask they have told K is not more than 1000000 or 1000000 digits??
if its digits will i even be able to store it in long long int.

jmwtechnomage: 2020-05-25 23:23:44

I get an NZEC error, and it's very hard to reproduce. I'm using a fuzzer called 'zuff' and to produce an NZEC with my million line file, I have to set the ratio to something like 1 in 10 bytes being bad, whereupon I get an error from data falling outside of the utf-8 range. I could maybe fix that by telling SBCL not to use UTF-8 somehow (maybe setting it to ascii?) but this appears to be well outside the scope of the problem we are given. We are not told whether data is in ascii or UTF-8, we are not told the format of the files used for the inputs (windows style EOF maybe?).

This problem is supposed to be about palindromes. If the problem is really about figuring out what bad data they are giving us, or making a program secure against non UTF-8 inputs, or something like that, they should tell us. I can feed my program 1,000,000 lines of input, containing 65,000 bytes of random data, and still not produce an NZEC. That should be sufficient for a program that is only designed to convert numbers into palindromes.

I'm doing this exercise in Common Lisp, a high level language. People doing this challenge in C probably have an easier time with it, because in C it might not be so unusual to filter inputs for a small program at the very moment the program receives them. Of course this is probably doable in Common Lisp, but I came here to do a palindromes programing challenge to increase my (beginner's level) knowledge of CL, not to learn to build a secure web server.

If I was building a secure web server, or a database server, or writing a kernel, then yes, I would need to do the work, fuzz testing the inputs at a low level to make sure the program meets it's design criteria - security - in those cases. I don't need to write a palindromes program to a standard developers don't even apply when they are building low level utilities like the ones in GNU Coreutils. If I emailed the makers of coreutils and told them 'ls' doesn't handle characters outside the UTF-8 range properly, they would probably need some more information before they were convinced it was a bug. Like 'Ok, what particular bytes are you talking about'?. They don't build 'ls' like a secure webserver because it's not one. And by the same token, a palindromes program is not a secure webserver either. It doesn't need to be secure against arbitrarily bad data.

surfeyone: 2020-05-24 00:26:44

0 -> 1
1 -> 2
2 -> 3
...
9 -> 11
99 -> 101
999 -> 1001
9898 -> 9999

kauai68: 2020-05-17 16:48:29

There are no leading zeros.

wahidmshafin: 2020-05-16 21:00:15

Try for these test cases
0012100-->12121
0003-->4

You need to get rid of the leading zeros

kauai68: 2020-05-10 18:28:28

I've got AC and I don't think that the implementation is difficult. Nice C++ code needs less than 80 lines of code.

Last edit: 2020-05-10 18:29:45
khoaph: 2020-05-10 03:34:49

Thanks @trulyness for the extra test cases
Got some wa because of not having awared of them.

Last edit: 2020-05-10 03:36:16
manishsaini4u: 2020-05-09 05:30:08

can anyone explain what problem says?


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%
467 16