VM7WC '16 #1 Gold - Russian Palindrome Cultivation

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 0.6s

Memory limit: 64M

Author:

JeffreyZ

Problem type

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 by 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$ ~N~, find the smallest integer authentic Russian palindrome that is larger than $N$ ~N~.

Input Specification

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

Output Specification

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

Sample Input 1

Sample Output 1

Sample Input 2

99897979878689789897

Sample Output 2

99897979888897979899

Comments

0

minecraftyugi commented on Jan. 13, 2016, 10:58 p.m. ← edited →

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

Edit: nvm it is

0

JeffreyZ commented on Jan. 14, 2016, 12:14 a.m.

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