Google Code Jam 2008 - Juice
Xem PDFBạn đang tổ chức một bữa tiệc. Để chuẩn bị, bạn đang pha chế một loại đồ uống bằng cách trộn ba loại nước trái cây khác nhau: Táo (Apple), Chuối (Banana) và Cà rốt (Carrot). Hãy gọi các loại nước trái cây này là \(A\), \(B\) và \(C\).
Bạn muốn quyết định tỷ lệ của mỗi loại nước trái cây trong đồ uống sao cho số lượng người tham dự bữa tiệc thích đồ uống đó là lớn nhất có thể.
Mỗi người có một tỷ lệ tối thiểu cho mỗi loại trong số 3 loại nước trái cây mà họ muốn có trong đồ uống. Họ sẽ chỉ thích đồ uống nếu tỷ lệ của mỗi loại nước trái cây trong đồ uống lớn hơn hoặc bằng tỷ lệ tối thiểu của họ đối với loại nước trái cây đó.
Hãy xác định số lượng người tối đa mà bạn có thể làm hài lòng.
Dữ liệu vào
- Một dòng chứa số nguyên \(T\), số lượng bộ dữ liệu trong file đầu vào.
Với mỗi bộ dữ liệu:
- Một dòng chứa số nguyên \(N\), số lượng người đi dự tiệc.
- \(N\) dòng, mỗi dòng dành cho một người, chứa ba số cách nhau bởi dấu cách "\(A\) \(B\) \(C\)", cho biết tỷ lệ tối thiểu của mỗi loại nước trái cây mà họ muốn trong đồ uống. \(A, B\) và \(C\) là các số nguyên từ \(0\) đến \(10000\) (bao gồm cả hai đầu), cho biết tỷ lệ tính theo phần mười nghìn (\(1/10000\)). \(A + B + C \le 10000\).
Dữ liệu ra
- \(T\) dòng, mỗi dòng cho một bộ dữ liệu theo thứ tự xuất hiện trong file đầu vào, mỗi dòng chứa chuỗi "Case #X: Y" trong đó X là số thứ tự của bộ dữ liệu (bắt đầu từ 1) và Y là số người tối đa sẽ thích đồ uống của bạn.
Ràng buộc
- \(1 \le T \le 12\)
Phân nhóm
- Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le N \le 10\)
- Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le N \le 5000\)
Điểm các phân nhóm
Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Test Set 1 | 3/13 | 23,08% |
| Test Set 2 | 10/13 | 76,92% |
Ví dụ
Ví dụ 1
Input
3
3
10000 0 0
0 10000 0
0 0 10000
3
5000 0 0
0 2000 0
0 0 4000
5
0 1250 0
3000 0 3000
1000 1000 1000
2000 1000 2000
1000 3000 2000Output
Case #1: 1
Case #2: 2
Case #3: 5Note
Trong trường hợp đầu tiên, đối với mỗi loại nước trái cây, chúng ta có một người muốn đồ uống được pha hoàn toàn từ loại nước trái cây đó! Rõ ràng chúng ta chỉ có thể làm hài lòng một trong số họ.
Trong trường hợp thứ hai, chúng ta có thể đáp ứng bất kỳ hai trong ba sở thích.
Trong trường hợp thứ ba, tất cả năm người sẽ thích đồ uống nếu chúng ta pha nó bằng cách chia đều một phần ba cho mỗi loại nước trái cây.
Nguồn
Google Code Jam 2008, Chung kết thế giới, bài Juice.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2008 - World Finals (15 Tháng 11., 2008)
Bình luận