[EASY][PALIN] The Next Palindrome - All About Free

Problem

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

Limitation

Time limit: 2s-9s
Source limit: 50000B
Memory limit: 1536MB

Solution

不知道为什么, 总是提示超时, 所以暂时先这样了. 因为谢了一些teat cases, 所以代码可能有一些奇怪的函数.

大概的思路就是先根据字符串前半段生成回文, 然后再做进位处理, 进位的思路就是给最中间的一位/两位加一, 如果存在'9', 则设置为'0', 并且在之后那一位/两位加一.

Golang代码:

package main

import (
    "fmt"
    "strconv"
)

var t, l int
var k [1000001]int

func IsPalindrome(n string) bool {
    s := n
    l := len(s)
    if n == "" || n[0] == '0' {
        return false
    }
    var left, right string
    switch {
    case l%2 == 0:
        left = s[:l/2]
        right = s[l/2:]
    case l%2 != 0:
        left = s[:l/2]
        right = s[l/2+1:]
    }
    for i, j := 0, len(right)-1; i < len(left); i, j = i+1, j-1 {
        if left[i] != right[j] {
            return false
        }
    }
    return true
}

func GetNumberString(s, e int) string {
    ret := ""
    for i := s; i < e; i++ {
        if i == 0 && k[i] == 0 {
            continue
        }
        ret = ret + strconv.Itoa(k[i])
    }
    return ret
}

func NextPalindrome_(str string) string {
    var c rune
    l = 1
    k[0] = 0
    for _, c = range str {
        k[l] = int(c) - '0'
        l++
    }
    return NextPalindrome()
}

func NextPalindrome() string {
    var str = ""
    var i, j int
    var lift bool = true
    if l == 2 {
        switch k[1] {
        case 9:
            return "11"
        default:
            return strconv.Itoa(k[1] + 1)
        }
    }

    for i = 1; i <= l/2; i++ {
        j = l - i
        if k[i] > k[j] {
            lift = false
        } else if k[i] < k[j] {
            lift = true
        }
        k[j] = k[i]
    }
    //  fmt.Println(GetNumberString(0, l))
    i--
    if lift {
        if k[j] == 9 && k[i] == 9 {
            for k[j] == 9 && k[i] == 9 {
                k[j], k[i] = 0, 0
                i--
                j++
            }
            if i == 0 {
                str = GetNumberString(0, l)
                if str[0] != '0' {
                    return str
                }
            }
        }

        if i == 0 {
            j--
        }
        if i != j {
            k[i]++
            k[j]++
        } else {
            k[i]++
        }
    }

    str = GetNumberString(0, l)

    return str
}

func main() {
    fmt.Scanln(&t)
    for i := 0; i < t; i++ {
        var c rune
        var str string
        l = 1
        k[0] = 0
        fmt.Scanln(&str)
        for _, c = range str {
            k[l] = int(c) - '0'
            l++
        }
        fmt.Print(NextPalindrome())
        if t-i != 1 {
            fmt.Println()
        }
    }
}

Submission result

时间不通过…