回文數

題目詳情

如果一個數正着讀和反着讀一樣大，則這個數叫做回文數，例如121是回文數，123454321是回文數。

現給定一個正整數x，輸出一個回文數y，要求y > x，并且組成x的所有數字之和與組成y的所有數字之和相等，以及y > x。

x在10^1000以内，因為數字較大，我們用字元串作為輸入和輸出。

如果無解，請輸出Impossible。如果有多個y，輸出最小的那個。

例如：

輸入919，輸出14941

輸入1，輸出Impossible

class Program
    {
        static void Main(string[] args)
        {
            string str = "919";
            int sum = Sum(str);

            if (str == "1" || str == "0" || str[0] == '-')
            {
                Console.WriteLine("Impossible");
            }

            do
            {
                str = Next(str);

                if (IsHuiWen(str) && Sum(str) == sum)
                {
                    Console.Write(str);
                    break;
                }

            } while (true);

            Console.Read();
        }

        /// <summary>
        /// Sum of each digit in a string.
        /// </summary>
        /// <param name="str">The string.</param>
        /// <returns></returns>
        static int Sum(string str)
        {
            int s = 0;

            int low = 0;

            while (low < str.Length)
            {
                s += str[low++] - '0';
            }

            return s;
        }

        /// <summary>
        /// whether a string is huiwen.
        /// </summary>
        /// <param name="str">The string.</param>
        /// <returns></returns>
        static bool IsHuiWen(string str)
        {
            int low = 0;
            int high = str.Length - 1;

            while (low < high)
            {
                if (str[low++] != str[high--])
                    return false;
            }

            return true;
        }

        /// <summary>
        /// String plus 1.
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        static string Next(string str)
        {
            char[] cs = new char[str.Length + 1];

            int i = str.Length - 1;
            int j = 0;
            int a = 1;
            int t = 0;

            while (i >= 0)
            {
                t = str[i--] - '0' + a;
                cs[j++] = (t % 10).ToString()[0];
                a = t / 10;
            }

            if (a == 1)
            {
                cs[j] = '1';
            }

            string s = "";

            int high = cs.Length - 1;

            while (high >= 0)
            {
                if (cs[high] == '\0')
                    high--;
                else
                    break;
            }

            while (high >= 0)
            {
                s += cs[high--];
            }

            return s;
        }
    }