3. Google Code Jam 2021 - Moons and Umbrellas
Cody-Jamal đang thực hiện tác phẩm nghệ thuật trừu tượng mới nhất của mình: một bức tranh tường gồm một hàng trăng khuyết và những chiếc ô đóng. Không may, những kẻ săn bản quyền tham lam cho rằng trăng khuyết trông giống chữ C viết hoa, ô đóng trông giống chữ J, và chúng nắm bản quyền đối với CJ và JC. Vì vậy, với mỗi lần CJ xuất hiện trong bức tranh, Cody-Jamal phải trả \(X\); với mỗi lần JC xuất hiện, anh phải trả \(Y\).
Cody-Jamal không muốn để chúng làm tổn hại tác phẩm nên sẽ không thay đổi bất cứ thứ gì đã vẽ. Tuy nhiên, anh quyết định có thể tô những chỗ còn trống một cách có chiến lược để giảm thiểu chi phí bản quyền.
Ví dụ, giả sử CJ?CC? là trạng thái hiện tại của bức tranh, trong đó C biểu diễn trăng khuyết, J biểu diễn ô đóng, còn ? biểu diễn một chỗ vẫn cần được vẽ thành trăng khuyết hoặc ô đóng. Anh có thể hoàn thiện bức tranh thành CJCCCC, CJCCCJ, CJJCCC hoặc CJJCCJ. Phương án thứ nhất và thứ ba phải trả \(X+Y\), còn phương án thứ hai và thứ tư phải trả \(2X+Y\).
Cho các chi phí \(X\), \(Y\) và một xâu biểu diễn trạng thái hiện tại của bức tranh, Cody-Jamal phải trả ít nhất bao nhiêu tiền bản quyền nếu hoàn thiện bức tranh theo cách tối ưu?
Dữ liệu vào
Dòng đầu chứa số lượng bộ dữ liệu \(T\). Tiếp theo là \(T\) dòng; mỗi dòng chứa hai số nguyên \(X\), \(Y\) và một xâu \(S\), lần lượt biểu diễn hai chi phí và trạng thái hiện tại của bức tranh.
Dữ liệu ra
Với mỗi bộ dữ liệu, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)), còn \(y\) là chi phí bản quyền nhỏ nhất Cody-Jamal phải trả cho một bức tranh đã hoàn thiện.
Ràng buộc
- \(1\le T\le100\).
- Mỗi ký tự của \(S\) là
C,Jhoặc?.
Phân nhóm
- Test Set 1 (Visible Verdict): \(1\le |S|\le10\); \(1\le X\le100\); \(1\le Y\le100\).
- Test Set 2 (Visible Verdict): \(1\le |S|\le1000\); \(1\le X\le100\); \(1\le Y\le100\).
- Thử thách thêm! Điều gì xảy ra nếu một số chủ bản quyền trả tiền cho Cody-Jamal để được quảng cáo thay vì nhận tiền? Việc Cody-Jamal được trả tiền được biểu diễn bằng chi phí âm.
- Test Set 3 (Hidden Verdict): \(1\le |S|\le1000\); \(-100\le X\le100\); \(-100\le Y\le100\).
Đ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 | 5/17 | 29,41% |
| Test Set 2 | 11/17 | 64,71% |
| Test Set 3 | 1/17 | 5,88% |
Ví dụ
Ví dụ 1
Input
4
2 3 CJ?CC?
4 2 CJCJ
1 3 C?J
2 5 ??J???Output
Case #1: 5
Case #2: 10
Case #3: 1
Case #4: 0Giải thích
- Bộ dữ liệu mẫu #1 chính là ví dụ trong đề. Chi phí nhỏ nhất là \(X+Y=2+3=5\).
- Trong bộ dữ liệu mẫu #2, Cody-Jamal đã hoàn thành tác phẩm nên không có lựa chọn nào khác. Bức tranh có hai
CJvà mộtJC. - Trong bộ dữ liệu mẫu #3, thay
?bằngChayJđều tạo đúng mộtCJ, tương ứng ở ký tự thứ hai và thứ ba hoặc ký tự thứ nhất và thứ hai. - Trong bộ dữ liệu mẫu #4, Cody-Jamal có thể hoàn thiện bức tranh hoàn toàn bằng
J. Vì xâu đó không chứaCJhayJC, chi phí bản quyền bằng \(0\).
Ví dụ bổ sung — Test Set 3
??? "Giải thích"
Ví dụ bổ sung sau thỏa ràng buộc Test Set 3 và **không** được chạy trên lời giải nộp.
!!! question "Ví dụ 2"
???+ "Input"
```sample
1
2 -5 ??JJ??
```
???+ success "Output"
```sample
Case #1: -8
```
??? "Giải thích"
Trong bộ dữ liệu này, Cody-Jamal có thể hoàn thiện tối ưu thành `JCJJCC` hoặc `JCJJJC`. Cả hai đều có một `CJ` và hai `JC`.
Nguồn
Google Code Jam 2021, Vòng loại, bài Moons and Umbrellas.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.