1. Google Code Jam 2022 - Duck, Duck, Geese
Trong trò chơi “Duck, Duck, Goose”, mọi người chơi trừ một người ngồi dưới sàn thành vòng tròn. Người còn lại đi quanh vòng, gọi từng người là “duck” cho tới khi chọn một người đang ngồi, chạm vào đầu họ và gọi là “goose”. Từ đó, “goose” đuổi theo người chọn và câu chuyện của trò chơi không còn liên quan tới bài này nữa.
Trong trò chơi mới “Duck, Duck, Geese”, người đi quanh thay vào đó chọn một đoạn liên tiếp gồm ít nhất hai, nhưng không phải tất cả, người đang ngồi làm “geese”. Hơn nữa, mỗi người đang ngồi đội một chiếc mũ. Mỗi mũ mang một trong \(C\) màu, đánh số từ \(1\) tới \(C\).
Với mỗi màu \(i\), số “geese” được chọn đang đội mũ màu \(i\) phải bằng \(0\), hoặc nằm trong đoạn \([A_i,B_i]\).
Hãy đếm số lựa chọn thỏa các yêu cầu. Hai lựa chọn được xem là khác nhau nếu tồn tại một người thuộc lựa chọn này nhưng không thuộc lựa chọn kia.
Dữ liệu vào
Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(N,C\): số người đang ngồi và số màu mũ. Tiếp theo là \(C\) dòng; dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\) như mô tả trên. Dòng cuối chứa \(N\) số nguyên \(P_1,P_2,\ldots,P_N\), nghĩa là người thứ \(j\) theo chiều kim đồng hồ, bắt đầu từ một người tùy ý, đội mũ màu \(P_j\).
Dữ liệu ra
Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\), và \(y\) là số đoạn liên tiếp gồm ít nhất \(2\) và nhiều nhất \(N-1\) người thỏa mọi yêu cầu về màu.
Ràng buộc
- \(1\le T\le100\).
- \(2\le C\le N\).
- \(0\le A_i\le B_i\le N\) với mọi \(i\).
- \(1\le P_j\le C\) với mọi \(j\).
Phân nhóm
- Test Set 1 (phán quyết hiển thị): \(3\le N\le1000\).
- Test Set 2 (phán quyết ẩn): \(3\le N\le10^5\).
Đ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 | 12/25 | 48% |
| Test Set 2 | 13/25 | 52% |
Ví dụ
Ví dụ 1
Input
3
3 2
1 1
1 1
1 1 2
5 2
1 1
1 2
1 2 1 2 2
3 3
1 2
1 2
2 2
1 1 3Output
Case #1: 2
Case #2: 9
Case #3: 1Giải thích
Trong test mẫu số 1, tổng số người được chọn làm geese phải là \(2\). Chỉ có ba cách chọn hai người, với cấu hình màu \([1,1]\), \([1,2]\), \([2,1]\). Cấu hình đầu có hai người đội màu \(1\) nên không hợp lệ; hai cấu hình còn lại hợp lệ. Đáp án là \(2\).
Test mẫu số 2 là hình trong đề, với màu \(1\) là vàng và màu \(2\) là xanh dương. Tổng số geese phải từ \(2\) tới \(3\), vì chọn \(4\) sẽ khiến ít nhất một màu vượt giới hạn. Với hai geese, yêu cầu duy nhất là không chọn hai người đều đội màu \(1\); cả năm lựa chọn như vậy đều hợp lệ. Với ba geese, các cấu hình là \([1,2,1]\), \([2,1,2]\), \([1,2,2]\), \([2,2,1]\) và \([2,1,2]\). Tất cả trừ cấu hình đầu đều hợp lệ, thêm bốn lựa chọn, tổng cộng \(9\).
Test mẫu số 3 cho thấy có thể tồn tại màu mũ không ai đội. Ở đây chỉ có một người đội màu \(3\), mà \(1\) không thuộc khoảng hợp lệ, nên cách hợp lệ duy nhất là chọn \(0\) người đội màu đó.
Nguồn
Google Code Jam 2022, Vòng 3, bài Duck, Duck, Geese.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
