trang chủ / đề bài / icpc23_mn_g

Bàn thắng

Đề bài

Mô tả

Quang và Trọng tham gia một trận bóng đá đặc biệt. Trong trận đấu này, mỗi người được phát ngẫu nhiên N quả bóng, mỗi quả có khối lượng ngẫu nhiên trong đoạn [1,1018].

Trận đấu diễn ra như sau: sân có N khung thành, đánh số từ 1 đến N. Quang đá trước, sút N quả bóng của mình vào N khung thành, mỗi khung thành đúng một quả (giả sử cả Quang và Trọng đều sút chính xác tuyệt đối). Quang được tự do chọn thứ tự sút các quả bóng. Sau khi Quang sút xong, Trọng xem khối lượng các quả bóng của Quang trong từng khung thành rồi quyết định sút N quả bóng của mình vào N khung thành, mỗi khung thành đúng một quả.

Kết thúc trận đấu, ở khung thành thứ i, người có quả bóng nặng hơn thắng và được i điểm (i=1,2,…,N). Nếu hai quả bóng trong khung thành thứ i nặng bằng nhau thì mỗi người được i/2 điểm. Người có tổng điểm cao hơn thắng trận.

Ví dụ, với N=3, Quang được các quả bóng nặng 1, 2, 4 và Trọng được các quả bóng nặng 1, 3, 5. Quang có thể sút các quả nặng 4, 2, 1 lần lượt vào khung thành 1, 2, 3. Sau khi xem các cú sút của Quang, Trọng có thể sút các quả nặng 3, 5, 1 lần lượt vào khung thành 1, 2, 3. Khi đó Quang được 1 điểm ở khung thành 1, 0 điểm ở khung thành 2 và 3/2=1,5 điểm ở khung thành 3, tổng cộng 2,5 điểm. Ví dụ này chỉ minh họa luật chơi: khi cả hai chơi tối ưu, Quang và Trọng có thể không sút như vậy.

Đến lượt mình, Trọng biết vị trí các quả bóng của Quang và chọn cách sút để tối đa hóa số điểm của mình. Còn khi đến lượt Quang, Quang không biết gì về các quả bóng của Trọng, nhưng biết chiến lược tối ưu của Trọng và biết khối lượng các quả bóng được phân bố đều và ngẫu nhiên. Vì vậy Quang chọn chiến lược để tối đa hóa kỳ vọng tổng điểm của mình.

Cho N, hãy tính kỳ vọng tổng điểm của Quang khi kết thúc trận đấu nếu cả hai chơi tối ưu như mô tả trên.

Dữ liệu vào

Một số nguyên N (1≤N≤100): số khung thành.

Dữ liệu ra

In ra một số thực là kỳ vọng tổng điểm của Quang khi kết thúc trận đấu, với đúng sáu chữ số sau dấu thập phân (làm tròn nếu cần).

Ràng buộc

  • 1≤N≤100

Ví dụ

Input Output Giải thích
1 0.500000 Mỗi người một quả bóng, Quang thắng với xác suất 1/2.
2 1.333333
100 598.874902

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