VM7WC '16 #1 Gold - Russian Palindrome Cultivation

View as PDF

Submit solution

Points: 10
Time limit: 0.6s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The palindrome (pronounced "ballin' drone") is a phrase or number that can be read the same way forwards or backwards. The palindrome was first discovered by Sarah Palin, who named the palindrome after herself after a night of observing the natives of Russia, a largely unexplored Asian landmass across the Pacific Ocean, from her Alaskan cottage. It is theorized and accepted by many members of the scientific community that all numbers in Russia are palindromes.

The reason for Russia's dependence on the palindrome is quite clear. During the 18th century, palindromes were primarily imported into Russia from Turkey, whose fertile soils and warm South American weather made it apt for growing it. However, in May of 1770, during the height of the Russo-Turkish War, Catherine the Great decreed a ban on importing palindromes to make Russia independent from the exports of its enemy, further modernizing the country by forcing Russians to create their own. As a result, non-palindromic numbers were forsaken in the Russian Empire, in order to conserve the necessary numbers and characters to create enough palindromes for the entire Russian populace. The day after Catherine's decree, the year was forcibly changed to 1771.

Today, a large portion of Russia's economy is still driven on the creation of palindromes, where it has become tradition to train young Russian children in palindrome cultivation. Google cofounder Sergey Brin grew and bottled his own premium palindromes as a child in the suburbs of Moscow. His aged palindromes have become a collector's item, and are valued at upwards of $5M USD.

Leo was fortunate enough to be able to experience one of Brin's palindromes first hand. For Project Feng, he's decided to educate all of its participants on the arcane art of Russian palindrome cultivation. Given a positive integer N, find the smallest integer authentic Russian palindrome that is larger than N.

Input Specification

The first and only line will contain the positive integer N. N will have at most 10^6 digits, another property that all numbers in Russia meet (but that's a story for another time). For 20% of all possible points, N will have less than 5 digits.

There is large input data in this problem.

Output Specification

On a single line, output the smallest palindrome greater than N.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2



  • 0
    minecraftyugi  commented on Jan. 13, 2016, 5:58 p.m. edited

    I'm just wondering, can this question be solved in Python?

    Edit: nvm it is

    • 0
      JeffreyZ  commented on Jan. 13, 2016, 7:14 p.m.

      If you check "Best Submissions", there are some solutions in Python.

  • 2
    r3mark  commented on Jan. 7, 2016, 8:47 p.m.

    Was there an error in the test cases or not?

    • 1
      DianaC  commented on Jan. 10, 2016, 9:48 a.m.

      @r3mark yes I believe so

    • 0
      ArvindB  commented on Jan. 10, 2016, 2:21 a.m.

      Mine didn't work either. Think its because of time limit.

      • 1
        DianaC  commented on Jan. 10, 2016, 9:49 a.m.

        @ArvindB You will need to change up your algorithm to a more efficient one so you don't TLE.