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 điểm; nếu hai số bằng nhau, mỗi con được điểm. Với hai con xúc xắc và , định nghĩa là kỳ vọng số điểm nhận được sau một lần gieo đấu với . Nếu , ta nói có lợi thế so với ; nếu , hai con xúc xắc hòa nhau. Ví dụ, nếu là con xúc xắc thứ nhất trong ví dụ thứ nhất và là con thứ hai, thì và , nên có lợi thế so với .
Cho hai con xúc xắc và sao cho có lợi thế so với , bạn muốn có con xúc xắc thứ ba tạo thành bộ ba không bắc cầu với hai con kia. Trong tất cả các con có lợi thế so với hoặc hòa với , hãy tính giá trị nhỏ nhất có thể của . Nếu giá trị này nhỏ hơn , 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 sao cho có lợi thế so với hoặc hòa với , hãy tính giá trị lớn nhất có thể của .
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à , con còn lại là .
Số nguyên đầu tiên trên mỗi dòng là (), số mặt của con xúc xắc. Tiếp theo là số nguyên ( với mọi ), 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 và giá trị lớn nhất của 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 . Đáp án của bạn được chấp nhận nếu sai số tuyệt đối không quá .
Ràng buộc
- với mỗi con xúc xắc.
- .
- 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ế () nên , . Với : (hòa) và . Với : và . |
| 4 9 3 7 5 3 4 2 3 |
0.500000000 0.500000000 | Con thứ nhất có lợi thế nên , . Không thể tạo được bộ ba không bắc cầu. |
Bình luận