trang chủ / đề bài / icpc22_mn_f

Kỳ vọng số token

Đề bài

Mô tả

Bạn được cho một bộ gồm n đồng xu, đồng xu thứ i khi tung có xác suất ra mặt ngửa là pi phần trăm. Trò chơi diễn ra như sau:

  • Bạn sẽ chơi k ván. Ban đầu bạn có x token.
  • Ở mỗi ván, bạn chọn một đồng xu trong bộ và luôn chọn mặt ngửa. Nếu đồng xu bạn chọn ở ván đó ra mặt ngửa thì bạn thắng ván đó, ngược lại bạn thua.
  • Nếu thắng một ván dùng đồng xu thứ i, bạn nhận thêm ai token (ai≥0).
  • Nếu thua một ván dùng đồng xu thứ i, bạn mất li phần trăm số token đang có.

Nhiệm vụ của bạn là chọn k đồng xu trong n đồng xu và thứ tự sử dụng chúng trong k ván để kỳ vọng số token cuối cùng là lớn nhất. Lưu ý rằng mỗi đồng xu chỉ được dùng một lần.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test.

  • Dòng đầu tiên của mỗi bộ test chứa ba số nguyên n, k và x (1≤k≤n≤100, 0≤x≤106).
  • Mỗi dòng trong n dòng tiếp theo mô tả đồng xu thứ i bằng ba số nguyên ai, li và pi (0≤ai,li,pi≤100).

Dữ liệu vào kết thúc bằng một dòng chứa 0 0 0, dòng này không cần xử lý.

Dữ liệu ra

Với mỗi bộ test, in ra trên một dòng kỳ vọng lớn nhất của số token cuối cùng, làm tròn đến đúng hai chữ số sau dấu thập phân. Đáp án được chấp nhận nếu chênh lệch so với đáp án của ban giám khảo không quá 0.01.

Ràng buộc

  • 1≤k≤n≤100
  • 0≤x≤106
  • 0≤ai,li,pi≤100
  • Mỗi file dữ liệu có không quá 100 bộ test.

Ví dụ

Input Output Giải thích
2 2 100
10 0 50
100 10 20
2 1 100
10 0 50
100 10 20
0 0 0
117.00
112.00
Bộ test thứ nhất: dùng đồng xu 2 trước, kỳ vọng sau ván đầu là 0.2·200+0.8·90=112; sau đó dùng đồng xu 1, kỳ vọng tăng thêm 0.5·10=5, được 117. Bộ test thứ hai chỉ chơi một ván, đồng xu 2 cho kỳ vọng 112.

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