Hướng dẫn giải của [200 đề thầy Đức] Bài 73: Chia kẹo
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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ó 4 gói kẹo với số lượng $a, b, c, d$. Cần chia hết 4 gói cho hai người sao cho hai người nhận số kẹo bằng nhau, mỗi gói thuộc về đúng một người. Số bộ dữ liệu $T \le 1000$ và mỗi số không vượt quá 100.
Sub 1: Vét cạn mọi cách chia — ~O(T \cdot 2^4)~
Với 4 gói có $2^4 = 16$ cách gán mỗi gói cho người thứ nhất hoặc người thứ hai. Thử hết 16 cách, nếu có cách nào để tổng của người thứ nhất bằng một nửa tổng thì trả lời YES. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int v[4];
for (int i = 0; i < 4; i++) cin >> v[i];
int total = v[0] + v[1] + v[2] + v[3];
bool ok = false;
// Vét cạn: thử mọi cách chia 4 gói thành hai nhóm (mỗi gói thuộc nhóm 0 hoặc 1).
for (int mask = 0; mask < 16; mask++) {
int s = 0;
for (int i = 0; i < 4; i++)
if (mask >> i & 1) s += v[i];
if (2 * s == total) ok = true; // hai người nhận số kẹo bằng nhau
}
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Sub 2: Kiểm tra các nhóm có thể — ~O(T)~
Tổng kẹo phải chẵn, vì mỗi người nhận đúng một nửa tổng. Khi tổng chẵn, gọi $h = \text{tổng} / 2$. Chỉ cần kiểm tra:
- Một gói bằng $h$ (khi đó gói còn lại gộp với ba gói kia cho người kia, tổng bằng nhau);
- Hai gói có tổng bằng $h$ (ví dụ $a + b$, $a + c$, $a + d$; các cặp còn lại là phần bù của các cặp này).
Ví dụ $1, 7, 11, 5$: tổng $24$, $h = 12$, và $1 + 11 = 12$ nên YES. Ví dụ $7, 3, 2, 5$: tổng $17$ lẻ nên NO.
Bẫy cần chú ý: phải kiểm tra tổng chẵn trước, nếu không phép chia $/2$ sẽ cho kết quả sai.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
int total = a + b + c + d;
// Hai người nhận bằng nhau khi tổng mỗi người là total / 2, nên total phải chẵn.
// Nhóm của người thứ nhất có thể là: một gói, hai gói hoặc ba gói (nhóm còn lại là phần bù).
// Ta chỉ cần kiểm tra các nhóm có tổng bằng một nửa.
bool ok = false;
if (total % 2 == 0) {
int half = total / 2;
if (a == half || b == half || c == half || d == half) ok = true; // 1 gói
if (a + b == half || a + c == half || a + d == half) ok = true; // 2 gói (ghép với gói còn lại)
}
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Bình luận