trang chủ / đề bài / icpcwf23_c

Ba loại xúc xắc

Đề bài

Mô tả

Xem chúng lăn này! Theo một câu chuyện nổi tiếng, Warren Buffett từng thách Bill Gates một trò chơi xúc xắc đơn giản. Ông có ba con xúc xắc; người chơi thứ nhất được xem xét chúng và chọn một trong ba con. Người chơi thứ hai sau đó chọn một trong hai con còn lại, rồi cả hai cùng gieo xúc xắc của mình đấu với nhau, ai ra số lớn hơn thì thắng. Warren mời Bill đi trước, nhưng điều này khiến Bill nghi ngờ nên ông chọn đi sau. Hóa ra đó là một lựa chọn sáng suốt: đây là những con xúc xắc không bắc cầu. Con thứ nhất có lợi thế khi gieo đấu với con thứ hai, con thứ hai có lợi thế khi gieo đấu với con thứ ba, nhưng con thứ nhất lại không có lợi thế khi gieo đấu với con thứ ba!

Một cách hình thức: ta định nghĩa một "con xúc xắc" là một vật có ít nhất một mặt, mỗi mặt ghi một số nguyên dương. Khi gieo một con xúc xắc, một trong các mặt của nó được chọn ngẫu nhiên đều. Khi hai con xúc xắc gieo đấu với nhau, con nào có mặt được chọn ghi số lớn hơn thì được 1 điểm; nếu hai số bằng nhau, mỗi con được 1/2 điểm. Với hai con xúc xắc D và D′, định nghĩa score(D,D′) là kỳ vọng số điểm D nhận được sau một lần gieo đấu với D′. Nếu score(D,D′)>1/2, ta nói D có lợi thế so với D′; nếu score(D,D′)=1/2, hai con xúc xắc hòa nhau. Ví dụ, nếu D là con xúc xắc thứ nhất trong ví dụ thứ nhất và D′ là con thứ hai, thì score(D,D′)=4/9 và score(D′,D)=5/9, nên D′ có lợi thế so với D.

Cho hai con xúc xắc D1 và D2 sao cho D1 có lợi thế so với D2, bạn muốn có con xúc xắc thứ ba D3 tạo thành bộ ba không bắc cầu với hai con kia. Trong tất cả các con D3 có lợi thế so với hoặc hòa với D1, hãy tính giá trị nhỏ nhất có thể của score(D3,D2). Nếu giá trị này nhỏ hơn 1/2, bạn có thể tạo được bộ ba không bắc cầu! Tương tự, trong tất cả các con D3 sao cho D2 có lợi thế so với hoặc hòa với D3, hãy tính giá trị lớn nhất có thể của score(D3,D1).

Dữ liệu vào

Dữ liệu vào gồm hai dòng, mỗi dòng mô tả một con xúc xắc. Một trong hai con (con thứ nhất hoặc con thứ hai) có lợi thế so với con còn lại. Con có lợi thế là D1, con còn lại là D2.

Số nguyên đầu tiên trên mỗi dòng là n (1≤n≤105), số mặt của con xúc xắc. Tiếp theo là n số nguyên fi (1≤fi≤109 với mọi 1≤i≤n), số ghi trên từng mặt.

Dữ liệu ra

In ra một dòng chứa giá trị nhỏ nhất của score(D3,D2) và giá trị lớn nhất của score(D3,D1) theo các điều kiện nêu trên. Hai giá trị này không nhất thiết phải dùng cùng một con xúc xắc D3. Đáp án của bạn được chấp nhận nếu sai số tuyệt đối không quá 10−6.

Ràng buộc

  • 1≤n≤105 với mỗi con xúc xắc.
  • 1≤fi≤109.
  • Một trong hai con xúc xắc có lợi thế so với con kia (không hòa).

Ví dụ

Input Output Giải thích
6 1 1 6 6 8 8
3 2 4 9
0.291666667 0.750000000 Con thứ hai có lợi thế (5/9) nên D1=(2,4,9), D2=(1,1,6,6,8,8). Với D3=(1,5,5,5): score(D3,D1)=1/2 (hòa) và score(D3,D2)=7/24. Với D3=(5,5,5,10): score(D3,D2)=1/2 và score(D3,D1)=3/4.
4 9 3 7 5
3 4 2 3
0.500000000 0.500000000 Con thứ nhất có lợi thế nên D1=(9,3,7,5), D2=(4,2,3). Không thể tạo được bộ ba không bắc cầu.

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