trang chủ / đề bài / icpcwf05_i

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á 1000 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ó p người và kéo dài d phút có thể xếp vào phòng có s chỗ ngồi và phải trả lúc T khi và chỉ khi p≤s và workshop kết thúc (lúc 14:00 cộng d phút) không muộn hơn T.

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 w. Mỗi dòng trong w dòng tiếp theo chứa hai số nguyên mô tả một workshop: số người tham gia p và thời lượng d (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 r. Mỗi dòng trong r dòng tiếp theo mô tả một phòng: số chỗ ngồi s, 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ố 0.

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ừ 1), 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

  • 1≤w≤1000, 1≤r≤1000.
  • 1≤p≤100, 1≤d≤300.
  • 1≤s≤100; 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á 100 bộ thử; tổng các w và tổng các r trong một file đều không quá 104.

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 20 người, 60 phút vừa phòng 30 chỗ dùng được 120 phút. Bộ 2: phòng duy nhất dùng được 50 phút; workshop 20 người quá dài, workshop 50 người quá đông, cả hai vào lều (20+50=70 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 30 người vào phòng 40 chỗ (kết thúc đúng lúc 15:00, vẫn hợp lệ), workshop 40 người vào phòng 50 chỗ; workshop 10 người vào lều. Bộ 2: phòng dùng được 299 phút, chỉ vừa workshop 99 người (99≤99, 299≤299).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0