3. Google Code Jam 2013 - Graduation Requirements
Trước khi tốt nghiệp Đại học Lập trình viên Tuyệt vời, sinh viên theo truyền thống phải thực hiện một số "yêu cầu tốt nghiệp". Một trong số đó là lái xe ngược chiều quanh một vòng xuyến giao thông. Với hầu hết mọi người, điều này đã đủ điên rồ rồi, nhưng như một thử thách thêm, bạn muốn xem liệu mình có thể đi ngược chiều quanh vòng xuyến nhiều vòng mà không dừng lại hay không.
Vòng xuyến giao thông bao gồm \(N\) giao lộ, cách đều nhau quanh vòng tròn. Một chiếc xe bình thường sẽ đi vào vòng xuyến tại một giao lộ, và sau mỗi giây, nó sẽ di chuyển đến giao lộ tiếp theo theo chiều ngược chiều kim đồng hồ, cho đến khi cuối cùng nó đến đích và rời đi.
Bạn đã quan sát các xe đi vào và rời khỏi vòng xuyến trong \(X\) giây. Với mỗi xe, bạn ghi lại thời điểm nó vào vòng xuyến, cũng như các giao lộ nó vào và ra. Tất cả các xe đều di chuyển ngược chiều kim đồng hồ với tốc độ 1 giao lộ mỗi giây. Mỗi chiếc xe bạn quan sát đều rời khỏi vòng xuyến trước khi quay trở lại giao lộ mà nó đã đi vào. Có nhiều làn đường trên vòng xuyến, vì vậy nhiều xe có thể chiếm cùng một vị trí tại cùng một thời điểm.
Nếu bạn đã lập kế hoạch vừa đúng, bạn có thể lái xe theo chiều kim đồng hồ trong vòng xuyến trong bao lâu? Bạn phải vào vòng xuyến tại một thời điểm nguyên \(>= 0\), rời đi tại thời điểm \(<= X\), và một khi bạn đã rời đi, bạn không được phép quay lại. Khi ở trong vòng xuyến, bạn phải di chuyển theo chiều kim đồng hồ với tốc độ 1 giao lộ mỗi giây. Bạn muốn chơi an toàn (theo cách an toàn nhất mà việc lái xe ngược chiều trên vòng xuyến có thể có), vì vậy bạn không bao giờ được chạm hoặc đi ngang qua một chiếc xe khác. Cụ thể, bạn không thể rời vòng xuyến tại một giao lộ mà một chiếc xe khác đang đi vào tại cùng thời điểm đó, và bạn không thể vào vòng xuyến tại một giao lộ mà một chiếc xe khác đang rời đi tại cùng thời điểm đó. Bạn có thể chọn thời điểm và địa điểm để vào và rời khỏi vòng xuyến.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo.
Dòng đầu tiên của mỗi bộ test mô tả số lượng xe \(C\) mà bạn đã quan sát. Dòng thứ hai chứa hai số nguyên, \(X\) và \(N\) — thời gian (tính bằng giây) mà bạn quan sát vòng xuyến, và số lượng giao lộ trên vòng xuyến. \(C\) dòng tiếp theo mô tả các xe bạn đã thấy. Mỗi dòng chứa ba số nguyên \(s_i\), \(e_i\) và \(t_i\) — giao lộ mà xe đi vào vòng xuyến, giao lộ mà nó rời đi và thời điểm nó đi vào. Các giao lộ được đánh số từ 1 đến \(N\), theo chiều ngược chiều kim đồng hồ (nghĩa là giao lộ số 2 là giao lộ tiếp theo theo chiều ngược chiều kim đồng hồ từ số 1).
Dữ liệu ra
Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số giây tối đa bạn có thể di chuyển trên vòng xuyến. Lưu ý rằng y có thể bằng 0 cả trong trường hợp bạn không thể vào vòng xuyến và trong trường hợp bạn có thể vào, nhưng không thể di chuyển dù chỉ một giao lộ.
Hãy nhớ rằng bạn được yêu cầu vào vòng xuyến tại một thời điểm được biểu thị bằng một số nguyên giây — bạn phải vào tại một thời điểm nguyên, và do đó đến mỗi giao lộ tại một thời điểm nguyên.
Ràng buộc
- \(1 \le T \le 100\)
- \(1 \le s_i, e_i \le N\)
- \(s_i \neq e_i\)
- \(0 \le t_i\)
- Mỗi chiếc xe được quan sát đều rời khỏi vòng xuyến tại thời điểm \(X\) hoặc sớm hơn.
Phân nhóm
- Small dataset (Test set 1 - Visible): \(3 \le N \le 10, 1 \le X \le 10, 0 \le C \le 10\).
- Large dataset (Test set 2 - Hidden): \(3 \le N \le 10^{10}, 1 \le X \le 10^{10}, 0 \le C \le 1000\).
Ghi chú chung
Lưu ý: Lái xe ngược chiều giao thông trên vòng xuyến thường không phải là một việc làm khôn ngoan và có thể gây hại cho bạn hoặc người khác. Google (và đặc biệt là Google Code Jam) khuyến khích bạn không nên thử điều này.
Đ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/25 | 28% |
| Test Set 2 | 18/25 | 72% |
Ví dụ
Ví dụ 1
Input
5
1
3 4
1 4 0
6
3 5
5 2 0
5 1 2
1 3 0
1 2 2
2 3 0
3 4 0
3
2 3
1 3 0
2 1 0
3 2 0
0
6 4
1
2 3
1 3 0Output
Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 6
Case #5: 0Note
Trong trường hợp mẫu đầu tiên, chúng ta có một chiếc xe, đi như trong hình ở đề bài. Có một số cách cho phép chúng ta đi ngược chiều trong một giây — ví dụ, chúng ta có thể vào tại giao lộ 1 lúc 1 giây (chúng ta không thể vào lúc 0 giây, vì xe kia đang ở đó), và đi đến giao lộ 4 (chúng ta không thể đi tiếp đến giao lộ 3, vì chúng ta sẽ đi ngang qua xe kia đang đi từ 3 đến 4). Một lựa chọn khác là vào tại giao lộ 4 lúc 0 giây, và đi đến giao lộ 3 (rồi rời đi).
Trong trường hợp mẫu thứ hai, chúng ta có thể di chuyển trong hai giây bằng cách vào giao lộ 5 lúc 1 giây, và đi ngược chiều đến giao lộ 3. Trong trường hợp mẫu thứ ba, chúng ta thậm chí không thể vào vòng xuyến - có xe ở tất cả các giao lộ tại mỗi giây nguyên. Trong trường hợp thứ tư không có xe nào, vì vậy chúng ta có thể vào vòng xuyến tại bất kỳ điểm nào lúc 0 giây và đi vòng quanh cho đến thời điểm 6. Trong trường hợp thứ năm, chúng ta có thể vào vòng xuyến, nhưng vì chỉ có ba giao lộ, chúng ta sẽ luôn va chạm với xe kia nếu cố gắng di chuyển đến giao lộ tiếp theo.
Nguồn
Google Code Jam 2013, Chung kết thế giới, bài Graduation Requirements.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.