Xem phim
Đề bài
Mô tả
Trong một kỳ nghỉ hiếm hoi, lớp của Sunflower tổ chức đi xem phim cùng nhau. Tuy nhiên, vì mùa lễ quá đông người, việc mua vé cho cả lớp xem cùng một suất chiếu rất khó khăn. Cuối cùng, cả lớp tìm được một rạp chiếu phim nằm khuất trong một con hẻm vắng. Rạp này có một hệ thống xếp chỗ ngồi đặc biệt, được mô tả như sau:
- Rạp có ghế đánh số từ đến . Sau khi mua vé, mỗi người được xếp ghế ngẫu nhiên. Cụ thể, một số nguyên dương được chọn từ đến với xác suất như nhau.
- Nếu và ghế còn trống, ghế đó được xếp cho người này. Ngược lại, được tăng thêm một và quá trình lặp lại.
- Nếu ở bước thứ hai không còn ghế nào ( vượt quá ), người đó phải đứng xem phim, hay còn gọi là vé đứng.
Lớp của Sunflower có học sinh (kể cả Sunflower), lần lượt mua vé và được xếp chỗ theo cách trên. Là một người yêu toán, Sunflower muốn biết xác suất để mọi học sinh trong lớp đều có ghế ngồi.
Dữ liệu vào
Dòng đầu tiên chứa số bộ dữ liệu ().
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên dương và ().
Dữ liệu ra
Với mỗi bộ dữ liệu, in trên một dòng hai số và , cho biết đáp án là . Đáp án phải được viết dưới dạng phân số tối giản (); nếu xác suất bằng , in ra 0 1.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 40 1 6 1 7 1 8 1 9 1 10 2 6 2 7 2 8 2 9 2 10 3 6 3 7 3 8 3 9 3 10 4 6 4 7 4 8 4 9 4 10 5 6 5 7 5 8 5 9 5 10 6 6 6 7 6 8 6 9 6 10 7 7 7 8 7 9 7 10 8 8 8 9 8 10 9 9 9 10 10 10 |
1 1 1 1 1 1 1 1 1 1 35 36 48 49 63 64 80 81 99 100 49 54 320 343 243 256 700 729 121 125 343 432 2048 2401 3645 4096 2000 2187 9317 10000 2401 3888 12288 16807 6561 8192 50000 59049 43923 50000 16807 46656 65536 117649 177147 262144 400000 531441 161051 200000 262144 823543 531441 1048576 1000000 1594323 1771561 2500000 4782969 16777216 20000000 43046721 58461513 100000000 100000000 387420489 214358881 500000000 2357947691 10000000000 |
Ví dụ của đề gốc. Với người duy nhất luôn có ghế. Với , : chỉ khi cả hai đều được chọn thì người thứ hai phải đứng, nên xác suất là . |
| 4 3 2 1 1 2 2 4 6 |
0 1 1 1 3 4 343 432 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: người nhưng chỉ có ghế nên xác suất là . Bộ thứ ba: trong cách chọn , chỉ có làm người thứ hai phải đứng. |
Bình luận