Hướng dẫn cho Bài 5: Cá Lớn Nuốt Cá Bé (THT B Hà Tĩnh 2026)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho \(n\) con cá, con cá thứ \(i\) có kích cỡ \(a_i\). Một con cá lớn hơn có thể ăn con cá nhỏ hơn (\(a_i > a_j\)). Sau khi ăn, kích cỡ con cá lớn sẽ tăng thêm một lượng bằng kích cỡ con cá đã ăn (\(a_i = a_i + a_j\)). Xác định xem mỗi con cá có thể trở thành con cá sống sót cuối cùng hay không.

Phân tích

  • Điều kiện để ăn: Cá chỉ ăn được cá có kích cỡ thực sự nhỏ hơn nó.
  • Chiến thuật tối ưu: Để một con cá có kích cỡ \(X\) có thể sống sót, nó nên ăn tất cả các con cá nhỏ hơn nó hiện có để tăng kích cỡ nhanh nhất có thể, sau đó mới hy vọng ăn được các con cá lớn hơn.
  • Tính chất đơn điệu: Nếu một con cá có kích cỡ \(X\) có thể sống sót, thì một con cá khác có kích cỡ \(Y > X\) cũng có thể sống sót (vì nó có xuất phát điểm tốt hơn). Do đó, sẽ tồn tại một ngưỡng kích cỡ \(K\), sao cho các con cá có kích cỡ \(a_i \ge K\) sẽ sống sót, và \(a_i < K\) sẽ không thể.
  • Trường hợp đặc biệt: Nếu tất cả các con cá có cùng kích cỡ và \(n > 1\), không con cá nào có thể ăn con cá nào, kết quả là tất cả đều không sống sót.

Cách làm đơn giản (Brute Force)

Ý tưởng

Với mỗi con cá \(i\), ta giả lập quá trình ăn:

  1. Sắp xếp các con cá còn lại theo thứ tự tăng dần.
  2. Luôn chọn con cá nhỏ nhất mà con cá hiện tại có thể ăn được.
  3. Nếu không thể ăn thêm con cá nào mà vẫn còn cá khác, con cá \(i\) thất bại.

Độ phức tạp

  • Thời gian: \(O(n^2)\) do duyệt qua \(n\) con cá, mỗi con cá mất \(O(n)\) để giả lập.
  • Đánh giá: Phù hợp cho \(n \leq 1024\) (Subtask 1).

Code Brute Force

C++
C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    string res = "";
    for (int i = 0; i < n; i++) {
        vector<long long> others;
        for (int j = 0; j < n; j++) {
            if (i != j) others.push_back(a[j]);
        }
        sort(others.begin(), others.end());

        long long current_size = a[i];
        bool can_win = true;
        vector<bool> eaten(n - 1, false);

        int count = 0;
        while (count < n - 1) {
            bool found = false;
            for (int j = 0; j < n - 1; j++) {
                if (!eaten[j] && current_size > others[j]) {
                    current_size += others[j];
                    eaten[j] = true;
                    count++;
                    found = true;
                }
            }
            if (!found) {
                can_win = false;
                break;
            }
        }
        res += (can_win ? 'T' : 'N');
    }
    cout << res << endl;
    return 0;
}
Python
Python
n = int(input())
a = list(map(int, input().split()))

res = []
for i in range(n):
    others = sorted([a[j] for j in range(n) if i != j])
    current_size = a[i]
    can_win = True
    eaten = [False] * (n - 1)

    count = 0
    while count < n - 1:
        found = False
        for j in range(n - 1):
            if not eaten[j] and current_size > others[j]:
                current_size += others[j]
                eaten[j] = True
                count += 1
                found = True
                # Vì đã sắp xếp, ta có thể ăn liên tục các con cá nhỏ
        if not found:
            can_win = False
            break

    res.append('T' if can_win else 'N')

print("".join(res))

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

Nhận xét

  1. Gọi mảng đã sắp xếp là \(b_1, b_2, \dots, b_n\) và mảng cộng dồn là \(S_i = \sum_{j=1}^i b_j\).
  2. Một con cá có kích cỡ ban đầu \(b_i\) sẽ ăn được tất cả các con cá có kích cỡ nhỏ hơn nó. Giả sử \(b_i\) là giá trị đầu tiên lớn hơn các giá trị trước đó, nó sẽ ăn hết các con cá từ \(b_1\) đến \(b_{i-1}\), tổng kích cỡ lúc này là \(S_i\).
  3. Sau đó, nó cần kiểm tra xem \(S_i\) có lớn hơn con cá tiếp theo chưa được ăn hay không. Nếu \(S_i > b_{i+1}\), nó ăn tiếp và kích cỡ trở thành \(S_{i+1}\). Quá trình lặp lại cho đến khi ăn hết hoặc bị chặn.
  4. Vì tính chất đơn điệu, ta dùng Tìm kiếm nhị phân để tìm vị trí \(idx\) nhỏ nhất trong mảng đã sắp xếp sao cho con cá \(b_{idx}\) có thể sống sót.

Thuật toán

  1. Sắp xếp mảng \(a\) thành mảng \(b\). Tính mảng tiền tố \(S\).
  2. Hàm check(mid):
    • Nếu \(b_{mid}\) là giá trị nhỏ nhất trong mảng (\(b_{mid} = b_1\)) và \(n > 1\), trả về false (vì không ăn được ai).
    • Bắt đầu với current_sum = S[mid] và vị trí đã ăn đến là p = mid.
    • Dùng upper_bound hoặc tìm kiếm nhị phân để tìm vị trí next_p xa nhất mà b[next_p] < current_sum.
    • Cập nhật p = next_p và current_sum = S[p].
    • Nếu p == n, trả về true. Nếu p không tăng thêm được nữa, trả về false.
  3. Tìm \(idx\) nhỏ nhất thỏa mãn check(idx).
  4. Ngưỡng kích cỡ tối thiểu là \(K = b_{idx}\). Các con cá \(a_i \ge K\) sẽ in ra T.

Độ phức tạp

  • Thời gian: \(O(n \log n)\) cho sắp xếp và \(O(\log n \cdot \log n)\) cho tìm kiếm nhị phân (mỗi lần check mất tối đa \(O(\log n)\) bước nhảy).
  • Bộ nhớ: \(O(n)\) để lưu mảng và tiền tố.

Code tham khảo

C++
C++
#include <bits/stdc++.h>
using namespace std;

int n;
vector<long long> a, b, s;

bool check(int idx) {
    if (n > 1 && b[idx] == b[1]) return false;
    long long cur = s[idx];
    int p = idx;
    while (p < n) {
        // Tìm con cá lớn nhất có thể ăn được (nhỏ hơn cur)
        int next_p = lower_bound(b.begin() + 1, b.end(), cur) - b.begin() - 1;
        if (next_p == p) break;
        p = next_p;
        cur = s[p];
    }
    return p == n;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    a.resize(n + 1);
    b.resize(n + 1);
    s.resize(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin() + 1, b.end());
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + b[i];

    int low = 1, high = n, ans_idx = n + 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (check(mid)) {
            ans_idx = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    long long min_val = (ans_idx <= n) ? b[ans_idx] : 2e18; // Giá trị ngưỡng
    for (int i = 1; i <= n; i++) {
        if (a[i] >= min_val) cout << "T";
        else cout << "N";
    }
    return 0;
}
Python
Python
import sys
import bisect

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    b = sorted(a)
    s = [0] * (n + 1)
    for i in range(n):
        s[i+1] = s[i] + b[i]

    def check(idx):
        # b[idx] là kích cỡ con cá đang xét (0-indexed)
        if n > 1 and b[idx] == b[0]:
            return False

        cur_sum = s[idx+1]
        p = idx
        while p < n - 1:
            # Tìm vị trí next_p sao for b[next_p] < cur_sum
            next_p = bisect.bisect_left(b, cur_sum) - 1
            if next_p <= p:
                break
            p = next_p
            cur_sum = s[p+1]

        return p == n - 1

    low = 0
    high = n - 1
    ans_idx = n

    while low <= high:
        mid = (low + high) // 2
        if check(mid):
            ans_idx = mid
            high = mid - 1
        else:
            low = mid + 1

    min_val = b[ans_idx] if ans_idx < n else float('inf')

    res = []
    for x in a:
        if x >= min_val:
            res.append('T')
        else:
            res.append('N')
    print("".join(res))

solve()

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.