Xin ý tưởng bài PALIN spoj

Bạn xây dựng nửa trên thì nửa dưới tự nó vào khuôn thôi. (N + O(1))

1. Viết một hàm kiểm tra tính thuận nghịch của một string
2. Viết một hàm nhập vào 1 số dạng string, trả về string tiếp theo.

Vậy thì chừng nào mới xong 1 triệu chữ số đấy.

Đề là: Tìm số đối xứng trong hệ thập phân đứng ngay sau số đã cho. Mình thì chắc chắn là O(N) vì số đối xứng không quá xa nhau, hay nếu cần điều chỉnh thì chỉ cần đúng một lần.

Ồ, vậy thì sẽ là thế này hử:

1. Viết hàm phân tách string thành 3 phần: nửa đầu, số lẻ ra ở chính giữa (nếu có) và nửa cuối.
2. Viết một hàm nhập vào 1 số dạng string, trả về string tiếp theo.
3. Viết hàm so sánh 2 số dạng string.
4. Tách số ban đầu thành 3 phần Head, Middle và Tail (phần T sẽ không dùng đến)
   4.1 Kiểm tra lại một số trường hợp đặc biệt
   4.2 Ghép H + M + H đảo ngược được A, nếu A lớn hơn số ban đầu thì return A
   4.3 Ghét H + M thành số Left
   4.3.1 Số tiếp theo L là Next
   4.3.2 Nếu N và L cùng độ dài thì tuỳ xem M là 1 chữ số hay là null để trả về kết quả.
   4.3.3 Nếu N dài hơn L thì cũng tuỳ xem M là như thế nào để trả về kết quả.

Độ phức tạp O(n) vì một số lệnh phải duyệt string.

Code mẫu trả về số đối xứng bằng C# (Hàm NextPalindrome)

string[] DivideString(string Input)//Từ Input, trả về mảng Output chứa H và M
{
    if (Input.Length == 1)
        return new string[] { "", Input };//Nếu không có dòng này, số có 1 chữ số sẽ trả về mảng {null, Input}, bất tiện cho việc tìm Length về sau.
    var Output = new string[2];
    for (int i = 0; i < Input.Length / 2; i += 1)
        Output[0] += Input[i];
    if (Input.Length % 2 != 0)
        Output[1] += Input[Input.Length / 2];
    return Output;
}

string NextNumber(string Input)//Hàm trả về số tiếp theo
{
    var Output = new List<char>(Input.Reverse());
    int Position = 0;
    while (Output[Position] == '9')
    {
        Output[Position] = '0';
        Position += 1;
        if (Position == Output.Count)
            Output.Add('0');
    }
    Output[Position] = (char)(Output[Position] + 1);
    Output.Reverse();
    return new string(Output.ToArray());
}

bool IsBigger(string Left, string Right)//Hàm kiểm tra xem Left có lớn hơn Right hay không
{
    if (Left.Length != Right.Length)
        return (Left.Length > Right.Length);
    for (int i = 0; i < Left.Length; i += 1)
        if (Left[i] != Right[i])
            return (Left[i] > Right[i]);
    return false;
}

string NextPalindrome(string Input)
{
    if (Input == null || Input == "")//Nếu số ban đầu là null hoặc rỗng thì trả về "0"
        return "0";
    while (Input.Length > 1)//Loại bỏ ký tự "0" ở đầu
        if (Input[0] == '0')
            Input = Input.Remove(0, 1);
    if (Input.Any(x => !Char.IsDigit(x)))//Nếu số ban đầu chứa ký tự không phải là chữ số thì chửi thằng nhập
        return "WTF dude?";
    var Material = DivideString(Input);
    var Output = Material[0] + Material[1] + new string(Material[0].Reverse().ToArray());
    if (IsBigger(Output, Input))
        return Output;
    else
    {
        var Left = Material[0] + Material[1];
        var Next = NextNumber(Left);
        if (Material[1] == null)
            if (Next.Length == Left.Length)
                Output = Next + new string(Next.Reverse().ToArray());
            else
                Output = Next.Substring(0, Left.Length) + Next.Last() + new string(Next.Substring(0, Left.Length).Reverse().ToArray());
        else
            if (Next.Length == Left.Length)
                Output = Next.Substring(0, Next.Length - 1) + Next.Last() + new string(Next.Substring(0, Next.Length - 1).Reverse().ToArray());
            else
                Output = Next.Substring(0, Left.Length) + new string(Next.Substring(0, Left.Length).Reverse().ToArray());
        return Output;
    }
}