Phân tích

Nhiều thí sinh đã gặp khó khăn ở bài toán này do ví dụ số 4. Giả sử \(n\) là \(1212\), sau khi chuyển 1 hoặc 3 chữ số, bạn sẽ nhận được \(2121\), do đó cặp \((1212, 2121)\) sẽ bị đếm hai lần nếu bạn đếm tất cả các phép chuyển có thể. Bạn có thể tránh điều này bằng cách thoát khỏi vòng lặp khi quay lại số ban đầu, điều này sẽ xảy ra sau khi chuyển 2 chữ số trong ví dụ trên.

Với tập dữ liệu nhỏ, bạn có thể kiểm tra đơn giản cho mỗi cặp \((n, m)\) thỏa mãn \(A \le n < m \le B\) xem nó có đáp ứng các điều kiện trong đề bài hay không, và liệu bạn có thể nhận được \(m\) bằng cách chuyển các chữ số từ cuối của \(n\) lên đầu mà không đổi thứ tự hay không. Để kiểm tra xem có thể tạo ra \(m\) từ \(n\) hay không, chỉ cần thử chuyển tất cả các nhóm chữ số có thể từ \(n\) và kiểm tra xem kết quả có bằng \(m\) không. Việc dịch chuyển chữ số có thể thực hiện bằng xử lý chuỗi hoặc các biểu thức toán học, cả hai đều sẽ chạy kịp thời gian giới hạn.

Tuy nhiên, giải pháp trên sẽ không kịp thời gian cho tập dữ liệu lớn. Vì vậy, đây là một giải pháp khác có thể chạy trong giới hạn thời gian: Với mỗi số \(n\) trong khoảng \(A \le n \le B\), hãy thử chuyển tất cả các nhóm chữ số có thể từ cuối lên đầu và kiểm tra xem số kết quả có thỏa mãn các điều kiện hay không. Nếu thỏa mãn, hãy tăng kết quả. Đừng quên tránh đếm cùng một số nhiều lần.

Cách cài đặt

Dưới đây là mã nguồn tham khảo:

int solve(int A, int B) {
    int power = 1, temp = A;
    while (temp >= 10) {
        power *= 10;
        temp /= 10;
    }
    int result = 0;
    for (int n = A; n <= B; ++n) {
        temp = n;
        while (true) {
            temp = (temp / 10) + ((temp % 10) * power);
            if (temp == n)
                break;
            if (temp > n && temp <= B)
                result++;
        }
    }
    return result;
}

Dựa trên phân tích chính thức của Google Code Jam.