trang chủ / đề bài / icpc25_mb_b

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:

  1. Rạp có K ghế đánh số từ 1 đến K. 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 L được chọn từ 1 đến K với xác suất như nhau.
  2. Nếu L≤K và ghế L còn trống, ghế đó được xếp cho người này. Ngược lại, L được tăng thêm một và quá trình lặp lại.
  3. Nếu ở bước thứ hai không còn ghế nào (L vượt quá K), người đó phải đứng xem phim, hay còn gọi là vé đứng.

Lớp của Sunflower có N 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 T (T≤50).

Mỗi dòng trong T dòng tiếp theo chứa hai số nguyên dương N và K (N,K≤200).

Dữ liệu ra

Với mỗi bộ dữ liệu, in trên một dòng hai số A và B, cho biết đáp án là A/B. Đáp án phải được viết dưới dạng phân số tối giản (B≥1); nếu xác suất bằng 0, in ra 0 1.

Ràng buộc

  • 1≤T≤50.
  • 1≤N,K≤200.

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 N=1 người duy nhất luôn có ghế. Với N=2, K=6: chỉ khi cả hai đều được chọn L=6 thì người thứ hai phải đứng, nên xác suất là 1−1/36=35/36.
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: 3 người nhưng chỉ có 2 ghế nên xác suất là 0. Bộ thứ ba: trong 4 cách chọn (L1,L2), chỉ có (2,2) làm người thứ hai phải đứng.

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