Google Code Jam 2017 - Play the Dragon
Xem PDFBạn là một chú rồng thân thiện đang chiến đấu để bảo vệ hang ổ khỏi một hiệp sĩ tham lam! Bạn có \(H_d\) điểm máu và sức tấn công \(A_d\); hiệp sĩ có \(H_k\) điểm máu và sức tấn công \(A_k\). Nếu tại bất kỳ lúc nào máu của bạn giảm xuống 0 hoặc thấp hơn, bạn bị hạ gục và thua ngay lập tức. Nếu máu của hiệp sĩ giảm xuống 0 hoặc thấp hơn, hắn bị hạ gục và bạn thắng!
Trận đấu diễn ra theo nhiều lượt. Trong mỗi lượt, bạn hành động trước và chọn thực hiện đúng một trong các hành động sau:
- Attack: giảm máu đối thủ một lượng bằng sức tấn công hiện tại của bạn.
- Buff: tăng sức tấn công của bạn thêm \(B\) trong toàn bộ phần còn lại của trận đấu.
- Cure: đưa máu của bạn trở lại \(H_d\).
- Debuff: giảm sức tấn công của đối thủ đi \(D\) trong toàn bộ phần còn lại của trận đấu. Nếu Debuff làm sức tấn công của đối thủ xuống dưới 0 thì đặt nó bằng 0.
Sau hành động của bạn, nếu hiệp sĩ vẫn còn nhiều hơn 0 máu, hắn sẽ thực hiện hành động Attack. Sau đó lượt kết thúc. Lưu ý rằng lượt bạn hạ hiệp sĩ vẫn được tính là một lượt, dù hắn không còn được hành động.
Các Buff cộng dồn: mỗi Buff tăng thêm \(B\) sức tấn công. Tương tự, các Debuff cũng cộng dồn.
Bạn muốn hạ hiệp sĩ nhanh nhất có thể (nếu có thể), để không đến muộn buổi nướng kẹo dẻo cùng dân làng trong lễ hội tối nay. Hãy xác định số lượt ít nhất để hạ hiệp sĩ, hoặc kết luận IMPOSSIBLE.
Dữ liệu vào
Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test gồm một dòng chứa sáu số nguyên \(H_d,A_d,H_k,A_k,B,D\) với ý nghĩa như trên.
Dữ liệu ra
Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE nếu không thể hạ hiệp sĩ, hoặc là số lượt ít nhất cần thiết.
Ràng buộc
- \(1 \le T \le 100\).
Phân nhóm
- Test Set 1 (Visible): \(1\le H_d,A_d,H_k,A_k\le100\); \(0\le B,D\le100\).
- Test Set 2 (Hidden): \(1\le H_d,A_d,H_k,A_k\le10^9\); \(0\le B,D\le10^9\).
Đ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 | 19/44 | 43,18% |
| Test Set 2 | 25/44 | 56,82% |
Ví dụ
Ví dụ 1
Input
4
11 5 16 5 0 0
3 1 3 2 2 0
3 1 3 2 1 0
2 1 5 1 1 1Output
Case #1: 5
Case #2: 2
Case #3: IMPOSSIBLE
Case #4: 5Note
Trong bộ test #1, bạn có 11 máu và 5 sức tấn công; hiệp sĩ có 16 máu và 5 sức tấn công. Một chuỗi hành động tối ưu là:
- Lượt 1: Attack, giảm máu hiệp sĩ xuống 11. Hiệp sĩ đánh lại, giảm máu bạn xuống 6.
- Lượt 2: Attack, giảm máu hiệp sĩ xuống 6. Hiệp sĩ đánh lại, giảm máu bạn xuống 1.
- Lượt 3: Cure, hồi máu lên 11. Hiệp sĩ đánh, giảm máu bạn xuống 6. Nếu lượt này bạn Attack, đòn tiếp theo của hiệp sĩ sẽ khiến bạn thua.
- Lượt 4: Attack, giảm máu hiệp sĩ xuống 1. Hiệp sĩ đánh, giảm máu bạn xuống 1.
- Lượt 5: Attack, giảm máu hiệp sĩ xuống -4. Bạn thắng ngay và hiệp sĩ không được đánh nữa.
Trong bộ test #2, một chuỗi tối ưu là Buff ở lượt 1, tăng sức tấn công lên 3; hiệp sĩ đánh làm máu bạn còn 1. Ở lượt 2, Attack làm máu hiệp sĩ về 0 và bạn thắng ngay.
Trong bộ test #3, hiệp sĩ chỉ cần hai đòn để hạ bạn, còn bạn không thể gây đủ sát thương đủ nhanh. Bạn có thể kéo dài trận đấu vô hạn bằng cách Cure sau mỗi đòn, nhưng không thể thực sự đánh bại hắn.
Trong bộ test #4, một chuỗi tối ưu là: Attack, Debuff, Buff, Attack, Attack.
Nguồn
Google Code Jam 2017, Vòng 1A, bài Play the Dragon.
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 1A (15 Tháng tư, 2017)
Bình luận