Hướng dẫn giải của [200 đề thầy Đức] Bài 80: Tổ chiến đấu mũi nhọn
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Có ~S~ tay súng, ~B~ chuyên gia bom mìn và ~N~ chiến sĩ thường. Mỗi tổ có đúng 3 người, trong đó có ít nhất 1 tay súng và 1 chuyên gia. Tìm số tổ tối đa.
Sub 1: Lập từng tổ — ~O(\text{số tổ})~, dùng khi ~S, B, N \le 1000~
Mỗi lần lập một tổ: lấy 1 tay súng, 1 chuyên gia, rồi lấy thêm 1 người. Ưu tiên chiến sĩ thường; nếu không còn thì lấy từ loại đang nhiều hơn để không làm cạn loại đang ít. Lặp đến khi không đủ người.
Nếu chỉ nộp sub này: đúng 3/21 test.
Sub 2: Công thức — ~O(1)~, dùng khi mọi trường hợp còn lại
Số tổ không vượt quá số tay súng ~S~, số chuyên gia ~B~, và ~\lfloor (S + B + N)/3 \rfloor~ vì mỗi tổ có 3 người. Ba điều kiện này cũng đủ nên đáp án là ~\min(S, B, \lfloor (S+B+N)/3 \rfloor)~.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng bộ ~S, B, N~. Nếu cả ba không vượt quá 1000 thì gọi sub1, ngược lại gọi sub2. Ví dụ: ~1 1 1~ cho 1; ~3 6 0~ cho 3; ~4 4 1~ cho 3.
#include <bits/stdc++.h>
using namespace std;
long long S, B, N; // so tay sung, chuyen gia bom min, chien si binh thuong
// Moi to can it nhat 1 tay sung va 1 chuyen gia, va 3 nguoi.
// Sub 1: vet can - lap tung to. Moi to lay 1 tay sung, 1 chuyen gia, roi them 1 nguoi bat ky:
// uu tien chien si binh thuong; neu khong con thi lay tu loai dang nhieu hon (de loai hiem
// khong bi can truoc). Dung khi S, B, N <= 1000.
void sub1() {
long long s = S, b = B, n = N, cnt = 0;
while (s >= 1 && b >= 1 && s + b + n >= 3) {
s--;
b--;
if (n > 0) n--;
else if (s >= b && s > 0) s--;
else b--;
cnt++;
}
cout << cnt << "\n";
}
// Sub 2: cong thuc. So to toi da bi chan boi so tay sung, so chuyen gia, va tong so nguoi / 3.
// Dap an = min(S, B, (S + B + N) / 3). O(1).
void sub2() {
cout << min(min(S, B), (S + B + N) / 3) << "\n";
}
int main() {
int T;
cin >> T;
while (T--) {
cin >> S >> B >> N;
if (S <= 1000 && B <= 1000 && N <= 1000) sub1();
else sub2();
}
return 0;
}
Bình luận