Tóm tắt đề bài

Cho một hàng gồm \(n\) người bạn với các tính cách khác nhau bước vào tiệc theo thứ tự:

• Hướng nội (I): Chỉ chịu ngồi ở bàn trống (bàn chưa có ai).
• Hướng ngoại (E): Chỉ chịu ngồi ở bàn đã có ít nhất một người.
• Hướng trung (A): Có thể ngồi ở bất kỳ bàn nào (cả bàn trống hoặc bàn đã có người).

Có tổng cộng \(x\) bàn, mỗi bàn chứa tối đa \(s\) chỗ ngồi. Ban đầu tất cả các bàn đều trống. Khi một người bước đến, ta có thể chọn xếp họ vào bàn thỏa mãn tính cách hoặc đuổi họ ra khỏi bữa tiệc. Khi đã ngồi xuống, họ không đổi chỗ.

Hãy tìm số lượng người tối đa có thể được sắp xếp chỗ ngồi hợp lệ.

Phân tích

• Giới hạn: Số truy vấn \(t \le 500\), số người \(n \le 3000\), số bàn \(x \le 3000\), số ghế mỗi bàn \(s \le 3000\). Tổng số lượng ký tự trong một test lớn có thể đạt tới hàng nghìn.
• Nhận xét quan trọng:
  • Những người tính cách I và E có quy tắc chọn bàn rất rõ ràng.
  • Người tính cách A (hướng trung) đóng vai trò linh hoạt: họ có thể hành xử như người I (mở bàn mới) hoặc như người E (ngồi vào bàn cũ).
  • Giả sử ta biết trước có chính xác \(m\) người mang tính cách A đóng vai trò như người I, thì \(r - m\) người A còn lại sẽ đóng vai trò như người E (với \(r\) là tổng số người mang tính cách A).
  • Khi cố định số lượng người A đóng vai trò là I, ta có thể duyệt qua từng người trong hàng từ trái sang phải và mô phỏng lại cách xếp chỗ một cách tối ưu cục bộ.

Hướng giải quyết (Tối ưu)

1. Đếm tổng số lượng người mang tính cách A trong chuỗi, gọi là \(r\).
2. Biến \(m\) (số người A đóng vai trò I) sẽ chạy từ \(0\) đến \(r\).
3. Với mỗi giá trị của \(m\), ta viết một hàm mô phỏng (eval) để tính số người tối đa có chỗ ngồi:
   • Duyệt qua từng người trong chuỗi:
     • Nếu gặp I: Nếu số bàn đang mở \(T < x\), ta mở bàn mới (\(T = T + 1\)) và tăng số người có chỗ.
     • Nếu gặp E: Nếu tổng số người hiện tại đang nhỏ hơn sức chứa tối đa của các bàn đang mở (\(ans < T \times s\)), ta xếp họ vào bàn cũ.
     • Nếu gặp A:
       • Nếu \(m > 0\) (vẫn còn định mức dùng A làm I), ta ưu tiên xử lý như I: nếu \(T < x\) thì mở bàn mới (\(T = T + 1\)) và giảm \(m\) đi 1.
       • Ngược lại, nếu hết định mức làm I, ta xử lý như E: nếu \(ans < T \times s\) thì xếp vào bàn cũ.
4. Lấy giá trị lớn nhất thu được qua tất cả các cách chọn \(m\) từ \(0\) đến \(r\).

Độ phức tạp

• Thời gian: Có \(r + 1\) cách chọn \(m\) (với \(r \le n\)), và mỗi lần mô phỏng mất \(O(n)\) bước. Do đó tổng thời gian cho một truy vấn là \(O(n^2)\). Với \(n \le 3000\), thuật toán này có thể tối ưu bằng cách nhận xét rằng kết quả theo hàm \(m\) có tính chất gần như đơn điệu hoặc có thể tối ưu hơn, nhưng với các giới hạn thực tế hoặc số test vừa phải, việc vét cạn số lượng A hóa I kết hợp tối ưu mô phỏng chạy rất tốt.
• Bộ nhớ: \(O(n)\) để lưu trữ chuỗi đầu vào.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

// Hàm mô phỏng: Tính số người có chỗ ngồi khi cho m người 'A' giả làm 'I'
int eval(const string &S, int m, int t, int s) {
    int T = 0;   // Số bàn đang được mở
    int ans = 0; // Số người đã có chỗ

    for (char c : S) {
        if (c == 'I') {
            if (T < t) {
                T++;
                ans++;
            }
        } else if (c == 'E') {
            if (ans < T * s) {
                ans++;
            }
        } else { // c == 'A'
            if (m > 0) { // Lượt này 'A' đóng vai trò là 'I'
                m--;
                if (T < t) {
                    T++;
                    ans++;
                }
            } else {       // Lượt này 'A' đóng vai trò là 'E'
                if (ans < T * s) {
                    ans++;
                }
            }
        }
    }

    return ans;
}

void solve() {
    int n, t, s;
    cin >> n >> t >> s;

    string S;
    cin >> S;

    // Đếm số lượng người Hướng trung (A)
    int r = 0;
    for (char c : S) {
        if (c == 'A') r++;
    }

    int ans = 0;
    // Thử nghiệm mọi khả năng từ 0 đến r người 'A' đóng vai trò 'I'
    for (int i = 0; i <= r; i++) {
        ans = max(ans, eval(S, i, t, s));
    }

    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

import sys

def eval_func(s_str, m, t, s):
    T = 0
    ans = 0
    for c in s_str:
        if c == 'I':
            if T < t:
                T += 1
                ans += 1
        elif c == 'E':
            if ans < T * s:
                ans += 1
        else:  # c == 'A'
            if m > 0:
                m -= 1
                if T < t:
                    T += 1
                    ans += 1
            else:
                if ans < T * s:
                    ans += 1
    return ans

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    num_queries = int(input_data[0])
    idx = 1

    out = []
    for _ in range(num_queries):
        n = int(input_data[idx])
        t = int(input_data[idx+1])
        s = int(input_data[idx+2])
        S = input_data[idx+3]
        idx += 4

        r = S.count('A')
        ans = 0
        for i in range(r + 1):
            ans = max(ans, eval_func(S, i, t, s))
        out.append(str(ans))

    print('\n'.join(out))

if __name__ == '__main__':
    solve()