Google Code Jam 2017 - Roller Coaster Scheduling
Xem PDFBạn đã tạo ra một tàu lượn siêu tốc mới sắp khai trương. Đoàn tàu có một hàng gồm \(N\) ghế, đánh số từ 1 đến \(N\) theo thứ tự từ trước ra sau; dĩ nhiên ghế càng gần phía trước càng giá trị. Khách hàng đã mua vé ngày khai trương. Mỗi vé cho phép một khách cụ thể đi một chuyến ở một ghế cụ thể. Một số khách có thể mua nhiều vé và mong được đi một chuyến cho mỗi vé.
Bạn cần quyết định ngày khai trương sẽ chạy bao nhiêu chuyến. Trong mỗi chuyến, mỗi ghế có thể có một khách và một số ghế có thể để trống. Không được xếp một khách vào nhiều hơn một ghế trong cùng chuyến, cũng không được xếp hai khách vào cùng một ghế trong một chuyến.
Bạn muốn giảm chi phí vận hành bằng cách dùng ít chuyến nhất mà vẫn thực hiện mọi vé. Để giảm số chuyến, bạn có thể thăng hạng tùy ý nhiều vé. Thăng hạng là đổi vé của một khách sang một ghế gần đầu tàu hơn, tức ghế có số nhỏ hơn. Bạn muốn thăng hạng ít vé nhất vì quá nhiều lần thăng hạng có thể khiến khách trở nên tham lam và đòi hỏi thêm trong tương lai.
Với vị trí và người mua của mọi vé đã bán, hãy tìm số chuyến nhỏ nhất để thực hiện tất cả vé khi được phép thăng hạng và xếp lịch tối ưu; đồng thời tìm số vé phải thăng hạng ít nhất để đạt số chuyến đó. Chẳng hạn, đổi vé của một khách trong một chuyến từ ghế 4 lên ghế 2 chỉ tính là một lần thăng hạng, không phải hai.
Dữ liệu vào
Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số nguyên: \(N\), số ghế; \(C\), số khách tiềm năng; và \(M\), số vé đã bán. Khách được đánh số từ 1 đến \(C\). Tiếp theo là \(M\) dòng, dòng thứ \(i\) chứa \(P_i\), vị trí ghế ghi trên vé thứ \(i\), và \(B_i\), mã số người mua vé đó.
Dữ liệu ra
Với mỗi bộ test, in Case #x: y z, trong đó x là số thứ tự bộ test (bắt đầu từ 1), y là số chuyến nhỏ nhất để thực hiện mọi vé khi thăng hạng và xếp lịch tối ưu, còn z là số lần thăng hạng nhỏ nhất để thực hiện mọi vé bằng đúng y chuyến.
Ràng buộc
- \(1\le T\le100\).
- \(2\le N\le1000\).
- \(1\le M\le1000\).
- \(1\le P_i\le N\).
- \(1\le B_i\le C\).
Phân nhóm
Test Set 1 (Visible): \(C=2\).
Test Set 2 (Hidden): \(2\le C\le1000\).
Đ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 | 7/21 | 33,33% |
| Test Set 2 | 14/21 | 66,67% |
Ví dụ
Ví dụ 1
Input
5
2 2 2
2 1
2 2
2 2 2
1 1
1 2
2 2 2
1 1
2 1
1000 1000 4
3 2
2 1
3 3
3 1
3 3 5
3 1
2 2
3 3
2 2
3 1Output
Case #1: 1 1
Case #2: 2 0
Case #3: 2 0
Case #4: 2 1
Case #5: 2 1Giải thích
Hai test cuối không xuất hiện trong Test Set 1.
Ở test 1, cả hai khách đều mua vé ghế 2. Không thể thực hiện cả hai vé trong một chuyến nếu giữ nguyên, nhưng thăng hạng một trong hai vé lên ghế 1 cho phép xếp cả hai vào cùng chuyến.
Test 2 tương tự, nhưng cả hai vé đều là ghế 1. Không thể thăng hạng các vé này hay đổi chúng xuống ghế kém hơn, nên buộc phải chạy hai chuyến riêng, mỗi khách một chuyến.
Ở test 3, cùng một khách mua vé cho cả hai vị trí. Khách đó buộc phải đi hai chuyến, nên không có lý do thăng hạng vé nào.
Ở test 4, có thể có cả khách lẫn vị trí không được gán vé nào. Có ba vé đã bán cho ghế 3. Chẳng hạn, nếu thăng hạng vé của khách 2 lên ghế 2, ta có thể chạy một chuyến với khách 1 ở ghế 2 và khách 3 ở ghế 3, rồi chuyến thứ hai với khách 2 ở ghế 2 và khách 1 ở ghế 3. Thăng hạng thêm cũng không thể giảm số chuyến vì khách 1 có hai vé và hai vé ấy luôn phải thuộc hai chuyến khác nhau.
Ở test 5, một nghiệm tối ưu là thăng hạng một trong các vé 3 1 thành 1 1.
Nguồn
Google Code Jam 2017, Vòng 2, bài Roller Coaster Scheduling.
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 2017 - Round 2 (13 Tháng năm, 2017)
Bình luận