1. Google Code Jam 2022 - Goose, Goose, Ducks?
Hội nghị Ngỗng quốc tế đầu tiên vừa kết thúc. Dù lẽ ra đây phải là một dịp vui, kết cục lại vừa ngọt ngào vừa cay đắng: ban tổ chức tìm thấy một tài liệu chứa kế hoạch chi tiết về một vụ thâm nhập của vịt. Giờ họ đang cố xác định nhóm thâm nhập trong số những người tham dự.
Tài liệu tìm được chứa danh sách \(M\) bộ ba số nguyên \((X_i,Y_i,C_i)\), nghĩa là các con vịt sẽ họp đúng \(C_i\) giây sau khi hội nghị bắt đầu tại điểm \((X_i,Y_i)\), nằm cách tâm sàn hội nghị \(X_i\) mét về phía đông và \(Y_i\) mét về phía bắc. Mỗi con ngỗng có thể có hoặc không có mặt tại đúng các điểm và thời điểm ấy, nhưng mọi con vịt chắc chắn đều có mặt.
Cả vịt lẫn ngỗng đều đi bộ với vận tốc tối đa một mét mỗi giây. Vì vậy, một người đang ở điểm \((x,y)\) tại thời điểm \(t\) có thể tới bất kỳ điểm dạng \((x+\Delta_x,y+\Delta_y)\) vào thời điểm \(t+\Delta_t\), miễn là
Vị trí của mỗi người tại thời điểm \(0\) có thể là một điểm bất kỳ, độc lập với những người khác.
Sau khi phát hiện tài liệu, cả nhóm tổ chức một phiên thẩm vấn nhằm nhận diện các con vịt. Trong phiên đó, những người tham dự lần lượt đưa ra các lời khai. Lời khai thứ \(j\) theo thứ tự được phát biểu do người \(A_j\) đưa ra; người này khẳng định rằng cả họ và người \(B_j\) đều ở điểm \((U_j,V_j)\) đúng \(D_j\) giây sau khi hội nghị bắt đầu. Các điểm trong lời khai có thể là hoặc không phải là nơi từng diễn ra cuộc họp vịt.
Lời khai của ngỗng luôn đúng, nhưng vịt có thể nói dối. Hơn nữa, vịt biết ai là vịt và ai là ngỗng. Để tránh dễ dàng bị bắt, vịt chỉ đưa ra những lời khai nhất quán với mọi lời khai mà ngỗng đã đưa ra trước đó. Lưu ý rằng các lời khai của ngỗng nhất quán với việc mọi con vịt đều có mặt ở tất cả các cuộc họp vịt.
Thông tin được cung cấp có thể không đủ để xác định tất cả các con vịt. Tuy nhiên, biết số vịt nhỏ nhất ít nhất cũng cho một cận dưới về mức độ hoạt động của vịt. Biết rằng có ít nhất một con vịt, hãy tìm số vịt nhỏ nhất có thể.
Nói một cách hình thức, một giả thuyết \(H\) là một cách phân hoạch tất cả người tham dự thành tập vịt (gọi là \(H\)-vịt) và tập ngỗng (gọi là \(H\)-ngỗng). \(H\) nhất quán với một tập lời khai \(S\) nếu tồn tại một quỹ đạo cho mỗi người, trên đó họ di chuyển với vận tốc không quá một mét mỗi giây, sao cho:
- mọi \(H\)-vịt đều có mặt tại mọi cuộc họp vịt; và
- với mỗi lời khai trong \(S\) nói rằng \(A\) thấy \(B\) ở điểm \(P\) tại thời điểm \(T\), quỹ đạo của cả \(A\) lẫn \(B\) đều đi qua điểm \(P\) tại thời điểm \(T\).
Một giả thuyết \(H\) là khả thi dưới tập lời khai \(S\) nếu:
- tập \(H\)-vịt không rỗng (tức thực sự có ít nhất một con vịt);
- tập con gồm mọi lời khai trong \(S\) do các thành viên \(H\)-ngỗng đưa ra nhất quán với \(H\) (tức lời khai của ngỗng luôn đúng); và
- với mỗi lời khai \(s\in S\) do một thành viên \(H\)-vịt đưa ra, nếu \(P\subseteq S\) là tập con các lời khai do thành viên \(H\)-ngỗng đưa ra trước \(s\), thì tồn tại một giả thuyết \(H'\) (có thể bằng hoặc khác \(H\)) sao cho \(\{s\}\cup P\) nhất quán với \(H'\) (tức vịt không mâu thuẫn với những lời khai trước đó của ngỗng).
Lưu ý rằng giả thuyết mà tập \(H\)-vịt chứa tất cả người tham dự luôn khả thi.
Hãy tìm kích thước nhỏ nhất của tập \(H\)-vịt trong mọi giả thuyết khả thi \(H\).
Dữ liệu vào
Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên \(N,M,S\), lần lượt là số người tham dự, số cuộc họp vịt và số lời khai. Mỗi dòng trong \(M\) dòng tiếp theo mô tả một cuộc họp vịt khác nhau bằng ba số nguyên \(X_i,Y_i,C_i\): cuộc họp diễn ra tại điểm \((X_i,Y_i)\) đúng \(C_i\) giây sau khi hội nghị bắt đầu. Cuối cùng, mỗi dòng trong \(S\) dòng cuối mô tả một lời khai. Dòng thứ \(j\) mô tả lời khai thứ \(j\) được đưa ra bằng năm số nguyên \(A_j,B_j,U_j,V_j,D_j\): người \(A_j\) nói rằng cả họ và người \(B_j\) đều ở điểm \((U_j,V_j)\) đúng \(D_j\) giây sau khi hội nghị bắt đầu.
Dữ liệu ra
Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số vịt nhỏ nhất có thể đã thâm nhập hội nghị.
Ràng buộc
- \(1\le T\le50\).
- \(-10^9\le X_i,Y_i\le10^9\) với mọi \(i\).
- \(1\le C_i\le10^9\) với mọi \(i\).
- \(C_i<C_{i+1}\) với mọi \(i\).
- \((X_i-X_{i+1})^2+(Y_i-Y_{i+1})^2\le(C_i-C_{i+1})^2\) với mọi \(i\).
- \(1\le A_j,B_j\le N\) và \(A_j\ne B_j\) với mọi \(j\).
- \(-10^9\le U_j,V_j\le10^9\) với mọi \(j\).
- \(1\le D_j\le10^9\) với mọi \(j\).
- \((A_j,B_j,U_j,V_j,D_j)\ne(A_k,B_k,U_k,V_k,D_k)\) với mọi \(j\ne k\).
Phân nhóm
Phân nhóm 1 (phản hồi hiện)
- \(2\le N\le50\).
- \(1\le M\le50\).
- \(1\le S\le50\).
Phân nhóm 2 (phản hồi ẩn)
- \(2\le N\le10^5\).
- \(1\le M\le10^5\).
- \(1\le S\le10^5\).
Điểm các phân nhóm
| Phân nhóm | Điểm Google Code Jam | Tỷ lệ điểm của bài |
|---|---|---|
| Phân nhóm 1 | 11/35 | 31,43% |
| Phân nhóm 2 | 24/35 | 68,57% |
Ví dụ
Ví dụ 1
Input
2
2 1 2
1 2 3
1 2 1 1 1
2 1 2 2 2
4 2 4
4 3 10
-4 -3 20
1 3 4 3 11
2 4 0 0 16
3 1 6 3 9
4 2 0 0 16Output
Case #1: 1
Case #2: 2Giải thích
Trong Test mẫu #1, giả thuyết người tham dự 1 là con vịt duy nhất là khả thi.
Trong Test mẫu #2, giả thuyết người tham dự 2 và 4 là hai con vịt duy nhất là khả thi. Lưu ý rằng có ít nhất một con vịt, nên giả thuyết mọi người tham dự đều là ngỗng không khả thi.
Nguồn
Google Code Jam 2022, Chung kết thế giới, bài Goose, Goose, Ducks?.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
