Các hội thảo
Đề bài
Mô tả
Hội nghị Holism California đầu tiên được tổ chức vào năm 1979 tại San Francisco. Chữ "California" khi đó hơi phóng đại, vì cả 23 người tham dự thực ra đều sống ở San Francisco. Vài năm sau, vào năm 1987, hội nghị đã thật sự mang tầm California với 337 người tham dự đến từ khắp bang. Từ đó, số người tham dự tăng nhanh như dung lượng chip nhớ. Năm 1993 hội nghị được đổi tên thành Hội nghị Holism Hoa Kỳ (2549 người tham dự), và lần đổi tên thứ hai (Hội nghị Holism Thế giới) diễn ra vào năm 1997, khi số người tham dự từ khắp thế giới đã lên tới 9973. Hội nghị mang tên hiện tại (Hội nghị Holism Thiên hà) từ năm 2003, sau một hồi tranh luận xem chữ "Thiên hà" có vô tình loại trừ các dạng sống ngoài thiên hà hay không. Dù vậy, năm sau đó mọi người đăng ký vẫn là người Trái Đất, mặc dù vài người khẳng định đã cảm nhận được sự hiện diện của người ngoài hành tinh.
Số hội thảo nhỏ (workshop) tăng theo số người tham dự. Với hội nghị sắp tới, ban tổ chức phải đối mặt với một bài toán xếp lịch rất thực tế nhưng rất khó chịu. Cho hội nghị năm 2005, ban tổ chức quyết định có không quá workshop diễn ra đồng thời. Dù vậy họ vẫn phải thuê mọi hội trường và phòng học có thể thuê được. Một số phòng chỉ được dùng trong một khoảng thời gian hạn chế.
Buổi sáng ngày đầu tiên là phiên khai mạc tại một sân vận động bóng đá, buổi chiều mọi người tham dự các workshop. Trước bữa trưa, mỗi người phải cho biết mình muốn tham gia workshop nào vào buổi chiều. Khi đó ban tổ chức có danh sách mọi workshop, gồm thời lượng và số người tham gia của từng workshop. Họ cũng có danh sách mọi phòng đã thuê, gồm sức chứa của từng phòng và thời điểm phải trả phòng đó. Với các thông tin này, ban tổ chức phải xếp mỗi workshop vào một phòng đủ chỗ và đủ thời gian. Vì bài toán này không phải lúc nào cũng có lời giải, ban tổ chức chuẩn bị thêm các lều dựng trong sân vận động. Các lều có sức chứa rất lớn, nhưng nóng nực và ồn ào. Vì vậy ban tổ chức muốn lịch xếp có ít workshop phải tổ chức trong lều nhất, tức là các workshop không được xếp vào phòng nào. Nếu có nhiều cách xếp cùng có số workshop trong lều ít nhất, ban tổ chức muốn số người tham dự các workshop trong lều là ít nhất.
Mọi workshop đều bắt đầu lúc 14:00 và diễn ra đồng thời, nên mỗi phòng chứa nhiều nhất một workshop. Mọi phòng đều sẵn sàng từ 14:00. Workshop có người và kéo dài phút có thể xếp vào phòng có chỗ ngồi và phải trả lúc khi và chỉ khi và workshop kết thúc (lúc 14:00 cộng phút) không muộn hơn .
Hãy tìm một lịch xếp như vậy (tốt nhất là trước khi bữa trưa kết thúc) và cho biết số workshop trong lều cùng số người tham dự các workshop trong lều.
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ thử. Mỗi bộ thử gồm hai phần: danh sách các workshop và danh sách các phòng đã thuê.
Danh sách workshop bắt đầu bằng một dòng chứa số workshop . Mỗi dòng trong dòng tiếp theo chứa hai số nguyên mô tả một workshop: số người tham gia và thời lượng (tính bằng phút).
Danh sách phòng bắt đầu bằng một dòng chứa số phòng . Mỗi dòng trong dòng tiếp theo mô tả một phòng: số chỗ ngồi , tiếp theo là thời điểm phải trả phòng, viết dưới dạng hh:mm theo đồng hồ 24 giờ (hh là giờ, mm là phút, mỗi phần gồm đúng hai chữ số).
Dữ liệu vào kết thúc bằng một dòng chứa duy nhất số .
Dữ liệu ra
Với mỗi bộ thử, in ra một dòng gồm số thứ tự của bộ thử (đánh số từ ), số workshop trong lều và số người tham dự các workshop trong lều, theo đúng định dạng của ví dụ: Trial k: a b (sau dấu hai chấm có hai dấu cách).
Ràng buộc
- , .
- , .
- ; thời điểm trả phòng nằm trong khoảng từ 14:01 đến 23:59 (tính cả hai đầu).
- Mỗi file có không quá bộ thử; tổng các và tổng các trong một file đều không quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 20 60 1 30 16:00 2 20 60 50 30 1 30 14:50 0 |
Trial 1: 0 0 Trial 2: 2 70 |
Bộ 1: workshop người, phút vừa phòng chỗ dùng được phút. Bộ 2: phòng duy nhất dùng được phút; workshop người quá dài, workshop người quá đông, cả hai vào lều ( người). |
| 3 30 60 40 120 10 30 2 40 15:00 50 16:00 2 100 300 99 299 1 99 18:59 0 |
Trial 1: 1 10 Trial 2: 1 100 |
Bộ 1: chỉ có hai phòng nên ít nhất một workshop vào lều. Xếp workshop người vào phòng chỗ (kết thúc đúng lúc 15:00, vẫn hợp lệ), workshop người vào phòng chỗ; workshop người vào lều. Bộ 2: phòng dùng được phút, chỉ vừa workshop người (, ). |
https://oj.chuyentin.pro/problem/icpcwf05_i
Bình luận