codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1700B.md (1813B)


      1 Source: https://codeforces.com/problemset/problem/1700/B
      2 
      3 B. Palindromic Numbers
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 During a daily walk Alina noticed a long number written on the ground. Now Alina wants to find some positive number of same length without leading zeroes, such that the sum of these two numbers is a palindrome.
     22 
     23 Recall that a number is called a palindrome, if it reads the same right to left and left to right. For example, numbers $121, 66, 98989$ are palindromes, and $103, 239, 1241$ are not palindromes.
     24 
     25 Alina understands that a valid number always exist. Help her find one!
     26 
     27 Input
     28 
     29 The first line of input data contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. Next, descriptions of $t$ test cases follow.
     30 
     31 The first line of each test case contains a single integer $n$ ($2 \leq n \leq 100\,000$) — the length of the number that is written on the ground.
     32 
     33 The second line of contains the positive $n$-digit integer without leading zeroes — the number itself.
     34 
     35 It is guaranteed that the sum of the values $n$ over all test cases does not exceed $100\,000$.
     36 
     37 Output
     38 
     39 For each of $t$ test cases print an answer — a positive $n$-digit integer without leading zeros, such that the sum of the input integer and this number is a palindrome.
     40 
     41 We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 2
     50 99
     51 4
     52 1023
     53 3
     54 385
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 32
     61 8646
     62 604
     63 ```
     64 
     65 Note
     66 
     67 In the first test case $99 + 32 = 131$ is a palindrome. Note that another answer is $12$, because $99 + 12 = 111$ is also a palindrome.
     68 
     69 In the second test case $1023 + 8646 = 9669$.
     70 
     71 In the third test case $385 + 604 = 989$.