Tóm tắt đề bài

Cho một số nguyên dương \(n\) (\(25 \le n \le 10^{18}\)). Bạn có thể thực hiện thao tác xóa một chữ số bất kỳ của \(n\). Nếu sau khi xóa, số thu được có các chữ số \(0\) ở đầu thì chúng sẽ tự động bị loại bỏ. Tìm số lần xóa ít nhất để số còn lại chia hết cho \(25\).

Phân tích

• Dấu hiệu chia hết cho 25: Một số chia hết cho \(25\) khi và chỉ khi hai chữ số tận cùng của nó là 00, 25, 50, hoặc 75.
• Ràng buộc: \(n\) có tối đa 18 chữ số (\(10^{18}\)), số lượng test case lên đến \(10000\). Do đó, với mỗi test case, ta cần một thuật toán có độ phức tạp cực thấp, lý tưởng là \(O(\text{số chữ số})\).
• Nhận xét quan trọng:
  • Để số thu được chia hết cho \(25\), ta chỉ cần quan tâm đến việc giữ lại hai chữ số tạo thành một trong bốn hậu tố: 00, 25, 50, 75.
  • Tất cả các chữ số nằm bên phải của chữ số hàng đơn vị (trong cặp hậu tố đã chọn) phải bị xóa.
  • Tất cả các chữ số nằm giữa chữ số hàng chục và chữ số hàng đơn vị (trong cặp hậu tố đã chọn) phải bị xóa.
  • Các chữ số đứng trước chữ số hàng chục không cần xóa (trừ khi chúng trở thành số \(0\) đứng đầu, nhưng đề bài đã nêu rõ các số \(0\) này tự động mất đi và không ảnh hưởng đến tính chia hết).

Hướng giải quyết

Thuật toán

1. Duyệt qua danh sách 4 hậu tố mục tiêu: \(S = \{\)"00", "25", "50", "75" \(\}\).
2. Với mỗi hậu tố \(t = t_0t_1\) trong danh sách \(S\):
   • Tìm vị trí của chữ số \(t_1\) trong số \(n\) tính từ phải sang trái. Gọi vị trí này là pos1.
   • Sau khi tìm thấy \(t_1\), tiếp tục tìm vị trí của chữ số \(t_0\) trong phần còn lại của số \(n\) (bên trái pos1). Gọi vị trí này là pos0.
   • Nếu tìm thấy cả hai chữ số:
     • Số lần xóa cần thiết để giữ lại cặp này là:
       (số chữ số bên phải t1) + (số chữ số nằm giữa t0 và t1).
     • Công thức cụ thể: Nếu \(n\) có độ dài \(L\), vị trí \(t_1\) là \(i\) và vị trí \(t_0\) là \(j\) (\(j < i\), tính từ trái sang phải bắt đầu từ 0), thì số lần xóa là: \((L - 1 - i) + (i - j - 1)\).
   • Nếu không tìm thấy đủ cả hai chữ số, trường hợp hậu tố này không khả thi.
3. Kết quả cuối cùng là số lần xóa nhỏ nhất trong tất cả các trường hợp khả thi của 4 hậu tố.

Ví dụ minh họa

Với \(n = 71345\):

• Thử hậu tố 75:
  • Tìm 5 từ phải sang: thấy ở vị trí cuối (index 4).
  • Tìm 7 bên trái số 5: thấy ở vị trí đầu (index 0).
  • Số chữ số cần xóa: (số bên phải 5: 0) + (số giữa 7 và 5: là 1, 3, 4 có 3 số) = \(0 + 3 = 3\).
• Các hậu tố khác không tìm đủ cặp.
• Kết quả: 3.

Độ phức tạp

• Thời gian: \(O(T \times 4 \times L)\), trong đó \(T\) là số test case, \(L\) là số chữ số của \(n\) (\(L \le 19\)). Với \(T=10000\), tổng số phép tính khoảng \(8 \times 10^5\), hoàn toàn thỏa mãn thời gian cho phép.
• Bộ nhớ: \(O(L)\) để lưu trữ chuỗi số \(n\).

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

// Danh sách 4 hậu tố chia hết cho 25
const string subseqs[] = { "00", "25", "50", "75" };
const int INF = 100;

/**

 * Hàm tính số lần xóa ít nhất để chuỗi s có hậu tố là t
 * @param s: chuỗi số ban đầu
 * @param t: hậu tố mục tiêu (00, 25, 50, hoặc 75)
 * @return: số lần xóa, hoặc INF nếu không thể tạo được
 */
int solve(string& s, string& t)
{
    int n = s.length();
    int ans = 0;
    int sptr = n - 1;

    // Bước 1: Tìm chữ số cuối cùng của hậu tố (t[1]) từ phải sang trái
    while (sptr >= 0 && s[sptr] != t[1])
    {
        sptr--;
        ans++; // Mỗi chữ số bên phải t[1] đều phải xóa
    }

    // Nếu không tìm thấy t[1]
    if (sptr < 0) return INF;

    // Bước 2: Tìm chữ số đầu tiên của hậu tố (t[0]) từ vị trí bên trái t[1]
    sptr--;
    while (sptr >= 0 && s[sptr] != t[0])
    {
        sptr--;
        ans++; // Mỗi chữ số nằm giữa t[0] và t[1] đều phải xóa
    }

    // Nếu không tìm thấy t[0] trả về INF, ngược lại trả về số lần xóa
    return sptr < 0 ? INF : ans;
}

int main()
{
    // Tối ưu nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while (t--)
    {
        string n;
        cin >> n;

        int min_deletions = INF;
        // Thử với tất cả 4 hậu tố có thể
        for (auto e : subseqs)
        {
            min_deletions = min(min_deletions, solve(n, e));
        }

        cout << min_deletions << '\n';
    }

    return 0;
}