trang chủ / đề bài / icpc20_reg_m

Đạ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 n chiếc cốc lên bàn và chọn hai hằng số k và x. 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 n cốc. Tổng lượng trà sữa thầy rót không vượt quá x 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.
  • k học sinh lên bục và uống trà sữa từ k 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ố i (1≤i≤n−k+1) và làm rỗng tất cả các cốc i,i+1,…,i+k−1.

Ở 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á x 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 2000 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 n, k và x 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 (0≤p≤n), trong đó p là số cốc bạn muốn rót trà sữa vào, tiếp theo là 2·p số: c1 v1 c2 v2…cp vp với 1≤ci≤n và 0≤vi≤x, nghĩa là bạn rót vi lít trà sữa vào cốc thứ ci. Các ci 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à c1 v1 c2 v2…cp vp 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 i (1≤i≤n−k+1) cho biết các học sinh uống trà sữa từ các cốc i,i+1,…,i+k−1. 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 2000 vòng. Nói cách khác, bạn phải in POUR ít hơn 2000 lần.

Với mỗi test, ban tổ chức đã tính trước một giá trị OPT, 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 OPT, bất kể các học sinh chơi thế nào. Giá trị OPT chỉ phụ thuộc vào n, k, x 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á (1+10−6)·x lít.
  • Khi trò chơi kết thúc, có một cốc chứa ít nhất (1−10−3)·OPT 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

  • 1≤n≤50.
  • 1≤k≤min(10,n).
  • 1≤x≤1000.

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 n=2, k=2, x=1: 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 1 lít vào cốc 1. Lượng lớn nhất khi kết thúc là 1. Đề gốc minh họa một cách chơi khác với cùng n, k, x: in POUR 2 1 0.6 2 0.3, đọc được 1 (hai cốc bị uống hết), rồi in FINAL 1 2 1, lượng lớn nhất cũng là 1.
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ả 4 cốc, nên chương trình dừng ngay và rót 10 lít vào cốc 1.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0