Chia Quà 4
Đề bài
Nhân dịp đi du lịch, Nam đã mua $n$ quả táo về làm quà cho hai người bạn thân là Tuấn và Sơn. Mỗi quả táo có trọng lượng là 100g hoặc 200g. Bây giờ Nam muốn chia đều $n$ quả táo trên thành hai phần có trọng lượng bằng nhau để chia cho bạn. Khi mua thì Nam quên kiểm tra điều này. Bạn hãy giúp Nam xem thử có thể chia $n$ quả táo trên thành hai phần có trọng lượng bằng nhau được không.
Dữ liệu vào:
- Dòng thứ nhất là số nguyên $n$ (số lượng các quả táo), dữ liệu vào đảm bảo $1 \le n \le 10^6$.
- Dòng thứ hai gồm $n$ số nguyên $a_1, a_2, \ldots, a_n$ là trọng lượng các quả táo mà Nam đã mua, dữ liệu vào đảm bảo chỉ có hai trường hợp $a_i = 100$ hoặc $a_i = 200$.
Dữ liệu ra: nếu Nam có thể chia được thì in là YES, nếu không chia được thì in là NO.
Subtask:
- 30% số test đầu tiên có $n \le 400$.
- 30% số test tiếp theo có $n \le 10^4$.
- 20% số test tiếp theo có $n \le 10^5$.
- 20% số test còn lại có $n \le 10^6$.
3
100 200 100YES4
100 100 100 200NO4
100 200 200 100YESGiải thích:
- Test 1: Phần một gồm quả táo thứ 1 và quả táo thứ 3, phần 2 là quả táo thứ 2 (mỗi phần 200g).
- Test 3: Phần một gồm quả táo thứ 1 và quả táo thứ 2, phần 2 là quả táo thứ 3 và thứ 4 (mỗi phần 300g).
Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesThì thực ra hỏi bài này dùng giải thuật gì thì mình cũng không biết phải trả lời thế nào luôn 😅 vì nó chỉ là một tư duy toán học nhìn ra được thôi, đặc biệt là nó rất thực tế. Tuy nhiên tưởng chừng đơn giản như vậy nhưng bạn nào không nhìn ra được vấn đề là sẽ phải đi xử lý rườm rà phức tạp cho bài này lắm.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Ý tưởngLiên hệ thực tế: chia tiền 1000 và 2000
Thì hãy liên hệ thực tế nhé: quả táo trọng lượng 100g thì hãy tương tự nó là tờ 1000 VNĐ, quả táo trọng lượng 200g thì hãy tương tự nó là tờ 2000 VNĐ. Nghĩa là số lượng quả táo 100g tương tự là số tờ tiền 1000 VNĐ và số lượng quả táo 200g tương tự là số tờ tiền 2000 VNĐ. Mình lấy mệnh giá tiền Việt Nam để các bạn dễ quen thuộc.
Ví dụ ta đang có $x_1$ tờ 1000 VNĐ và $x_2$ tờ 2000 VNĐ thì cần chia ra cho 2 người làm sao để số tiền mỗi người có được là bằng nhau? Tất nhiên chỉ được chia trong phạm vi 2 loại tờ tiền 1000 VNĐ, 2000 VNĐ đang có chứ không cho đổi sang tờ tiền mệnh giá khác nhé. Hãy tìm cách xem liệu có thể chia cho 2 người bằng nhau được không?
Trường hợp 1: cả hai đều chẵn
Ta sẽ thấy một điều rất dễ để nhìn ra: nếu số lượng 2 loại tờ tiền 1000 VNĐ, 2000 VNĐ đều là số chẵn (tức là $x_1$ và $x_2$ đều chẵn) thì chắc chắn luôn sẽ chia được, cụ thể mỗi người sẽ nhận được $\frac{x_1}{2}$ tờ 1000 VNĐ và $\frac{x_2}{2}$ tờ 2000 VNĐ.
Nếu không được như vậy, tức là $x_1$ hay $x_2$ có cái là số lẻ (hay cả 2 đều lẻ) thì lúc này sẽ phải xem xét có chia được hay không. Nếu có số lượng nào là số lẻ, tức là nếu chia số lượng đó đều ra cho 2 người thì sẽ bị dư ra 1 tờ mệnh giá đó, bởi nguyên tắc số lẻ thì % 2 (phép chia dư cho 2) sẽ luôn ra kết quả là 1. Ví dụ đang có 3 tờ thì chia ra mỗi người 1 tờ và dư 1 tờ; đang có 1 tờ thì mỗi người 0 tờ và dư 1 tờ. Vấn đề là liệu 1 tờ dư ra đó ta có thể chia làm sao để đều cho mỗi người một nửa không?
Trường hợp 2: tờ dư ra là tờ 2000 VNĐ
Nếu tờ tiền đang dư ra có mệnh giá 2000 VNĐ, nghĩa là mỗi người phải được một nửa, tức 1000 VNĐ. Vậy thì một cách chia rất thực tế dễ nhìn ra: một trong 2 người, ví dụ người A, sẽ chủ động đưa 1000 VNĐ cho người B, rồi người A nhận về tờ 2000 VNĐ đó. Như thế là mỗi người được thêm 1000 VNĐ thôi.
Vấn đề là muốn được như vậy thì 1 trong 2 người phải đang có tờ 1000 VNĐ thì mới thối lại được cho người kia. Còn nếu không có tờ 1000 VNĐ nào thì coi như không có cách nào chia được.
Trường hợp 3: tờ dư ra là tờ 1000 VNĐ
Còn nếu tờ tiền bị dư ra mà có mệnh giá là 1000 VNĐ thì thôi xác định sẽ chẳng có cách chia nào được, bởi lúc này mỗi người sẽ phải nhận 500 VNĐ, tức là người này phải đưa 500 VNĐ cho người kia rồi mới nhận về được tờ 1000 VNĐ. Nhưng mà ở đây ta chỉ có 2 loại tiền là 1000 VNĐ và 2000 VNĐ chứ làm gì có mệnh giá 500 VNĐ nên sẽ chẳng thể thối lại được.
Tóm lạiGiải thuật chỉ là vài câu if
Vậy tóm lại giải thuật lúc này là gì? Gọi $x_1$ là số lượng quả táo có trọng lượng 100g, $x_2$ là số lượng quả táo có trọng lượng 200g.
- Nếu $x_1$ là số lẻ thì kết luận NO.
- Ngược lại ($x_1$ là số chẵn) thì xét tiếp: nếu $x_2$ là số chẵn thì kết luận YES.
- Nếu $x_2$ là số lẻ thì cần đảm bảo có tồn tại tờ 1000 (quả 100g) để thối lại thì mới chia được. Lúc này $x_1$ đang chẵn, nên chỉ cần loại trừ trường hợp $x_1 = 0$ (vì 0 cũng là số chẵn): $x_1 \ne 0$ thì YES, còn $x_1 = 0$ thì NO.
| $x_2$ chẵn | $x_2$ lẻ | |
|---|---|---|
| $x_1$ lẻ | NO | NO |
| $x_1$ chẵn, $x_1 > 0$ | YES | YES |
| $x_1 = 0$ | YES | NO |
Việc thống kê số lượng 2 biến $x_1$, $x_2$ ta làm luôn ngay trong quá trình đọc dữ liệu input vào. Và cũng không cần mảng lưu trữ trọng lượng từng quả táo, mà chỉ cần biến $x$ đại diện đọc trọng lượng từng quả rồi kiểm tra điều kiện để tăng biến đếm $x_1$ hay $x_2$ tương ứng.
Minh hoạChia táo cho Tuấn và Sơn
Em nhập trọng lượng các quả táo (100 hoặc 200, tối đa 16 quả) rồi bấm Tiếp để xem từng bước đếm, xét chẵn lẻ và cách chia cụ thể cho 2 bạn:
CodeĐếm khi đọc + xét chẵn lẻ – O(N)
Source code các bạn tham khảo để nhìn thấy rõ với tất cả những gì mình đã phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, x, x1 = 0, x2 = 0;
cin >> n;
while(n--){
cin >> x;
if(x == 100){
x1++;
}
else{
x2++;
}
}
if(x1 % 2 != 0){
cout << "NO";
}
else{
if(x2 % 2 == 0){
cout << "YES";
}
else{
if(x1 != 0){
cout << "YES";
}
else{
cout << "NO";
}
}
}
return 0;
}n = int(input())
arr = list(map(int, input().split()))
x1 = x2 = 0
for x in arr:
if x == 100:
x1 += 1
else:
x2 += 1
if x1 % 2 != 0:
print("NO")
else:
if x2 % 2 == 0:
print("YES")
else:
if x1 != 0:
print("YES")
else:
print("NO")Đánh giá độ phức tạp của cách làm này:
Bài cho $n$ tối đa $10^6$ nên với cách làm trên cũng chỉ cần lặp qua đủ $n$ lần đọc dữ liệu input thôi. Trong trường hợp xấu nhất $n = 10^6$ thì vòng lặp cũng chỉ lặp $10^6$ lần, ít hơn rất nhiều so với ngưỡng giới hạn tiêu chuẩn 1 giây là $(3 \text{ đến } 5) \cdot 10^7$, cao lắm là $10^8$. Nên yên tâm sẽ không bị TLE nhé.
Thực ra cách làm ở trên có thể xem là tối ưu nhất rồi, sẽ không có cách nào tối ưu hơn được đâu. Vì mọi bài dù ít nhất cũng phải làm được bước đọc dữ liệu từ input, còn ở đây bài này chỉ cần đọc dữ liệu xong rồi qua vài câu lệnh kiểm tra điều kiện nữa là ra đáp án luôn, không cần phải lặp thêm gì nữa.
Nhận xét
Đăng nhận xét