Đại chiến trà sữa
Đề bài
Mô tả
Năm 2020, để phổ biến lập trình máy tính trong thế giới phù thủy, Trường Phù thủy và Pháp sư Hogwarts mời giáo sư Hạnh dạy một môn học mới: "Lập trình máy tính".
Để lớp học thêm hào hứng, giáo sư Hạnh mang đến lớp một lượng trà sữa thơm ngon vô hạn. Trong giờ ra chơi, thầy Hạnh và các học sinh sẽ chơi trò "đại chiến trà sữa".
Đầu tiên, thầy Hạnh đặt chiếc cốc lên bàn và chọn hai hằng số và . Ban đầu mọi cốc đều rỗng, và mỗi cốc chứa được lượng trà sữa vô hạn. Trò chơi gồm nhiều vòng, mỗi vòng diễn ra như sau:
- Thầy Hạnh rót trà sữa vào một số cốc trong cốc. Tổng lượng trà sữa thầy rót không vượt quá lít. Lượng trà sữa rót vào một cốc có thể không phải là số nguyên.
- học sinh lên bục và uống trà sữa từ cốc liên tiếp. Vì trà sữa quá ngon, các em uống hết sạch trà sữa trong các cốc đó. Nói cách khác, các em chọn một chỉ số () và làm rỗng tất cả các cốc .
Ở bất kỳ vòng nào, thầy Hạnh cũng có thể buộc trò chơi dừng ngay lập tức. Trong vòng cuối cùng này chỉ có bước thứ nhất diễn ra: thầy Hạnh vẫn rót không quá lít trà sữa vào một số cốc, nhưng không học sinh nào uống. Sau đó thầy chụp một bức ảnh để đăng lên Facebook. Để bức ảnh thật ấn tượng, thầy muốn khi trò chơi kết thúc, lượng trà sữa lớn nhất trong một cốc là lớn nhất có thể. Vì giờ ra chơi có hạn, thầy Hạnh phải dừng trò chơi trong vòng đầu tiên.
Hãy giúp thầy Hạnh đạt được mục tiêu, để bức ảnh của thầy nhận được thật nhiều lượt thích và thả tim!
Tương tác
Đầu tiên, chương trình của bạn đọc ba số nguyên , và như mô tả ở trên. Sau đó, ở mỗi vòng:
- Nếu muốn thầy Hạnh dừng trò chơi sau vòng này, hãy in
FINAL p(), trong đó là số cốc bạn muốn rót trà sữa vào, tiếp theo là số: với và , nghĩa là bạn rót lít trà sữa vào cốc thứ . Các phải đôi một khác nhau. Sau khi đọc dòng này, trình chấm dừng ngay lập tức và chương trình của bạn không được đọc thêm gì từ đầu vào chuẩn. - Ngược lại, in
POUR p, tiếp theo là với cùng ý nghĩa và ràng buộc như trên, chỉ khác là thầy Hạnh không dừng trò chơi sau vòng này. Sau đó trình chấm đưa cho bạn một số nguyên () cho biết các học sinh uống trà sữa từ các cốc . Chương trình của bạn cần đọc số này.
Chương trình của bạn phải in FINAL trong vòng vòng. Nói cách khác, bạn phải in POUR ít hơn lần.
Với mỗi test, ban tổ chức đã tính trước một giá trị , mà có thể chứng minh được rằng tồn tại chiến lược giúp thầy Hạnh làm cho lượng trà sữa lớn nhất trong một cốc khi kết thúc trò chơi đạt ít nhất , bất kể các học sinh chơi thế nào. Giá trị chỉ phụ thuộc vào , , và được giữ bí mật. Bạn vượt qua một test khi và chỉ khi cả hai điều kiện sau thỏa mãn:
- Ở mọi vòng, tổng lượng trà sữa được rót không vượt quá lít.
- Khi trò chơi kết thúc, có một cốc chứa ít nhất lít trà sữa.
Trình chấm là thích ứng: các học sinh có thể chọn cách uống khác nhau tùy theo những gì chương trình của bạn in ra.
Sau mỗi lần in, đừng quên xuống dòng và flush đầu ra: dùng fflush(stdout) hoặc cout.flush() trong C++, sys.stdout.flush() trong Python.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 1 | FINAL 1 1 1 | Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Ở đây , , : mỗi lần uống, các học sinh làm rỗng cả hai cốc, nên chương trình dừng ngay và rót lít vào cốc . Lượng lớn nhất khi kết thúc là . Đề gốc minh họa một cách chơi khác với cùng , , : in POUR 2 1 0.6 2 0.3, đọc được (hai cốc bị uống hết), rồi in FINAL 1 2 1, lượng lớn nhất cũng là . |
| 4 4 10 | FINAL 1 1 10 | Ví dụ bổ sung (không có trong đề gốc). Mỗi lần uống làm rỗng cả cốc, nên chương trình dừng ngay và rót lít vào cốc . |
Bình luận