trang chủ / đề bài / icpc22_mt_c

Sắp xếp thí sinh

Đề bài

Mô tả

Cho bảng xếp hạng hai vòng thi của n thí sinh trong một kỳ thi ACM/ICPC. Ta chắc chắn Elo của thí sinh A cao hơn Elo của thí sinh B khi A xếp hạng cao hơn B ở cả hai vòng, tức là r1A<r1B và r2A<r2B, trong đó r1A,r2A là thứ hạng của A ở vòng 1 và vòng 2 (tương tự với B). Trong các trường hợp còn lại thì không chắc chắn.

Hãy đếm số cách chọn ra k thí sinh sao cho có thể sắp xếp k thí sinh này theo thứ tự Elo giảm dần một cách chắc chắn (mọi cặp thí sinh được chọn đều so sánh chắc chắn được với nhau).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k (1≤n≤105, 1≤k≤10) là số thí sinh và số thí sinh cần chọn.

Mỗi dòng trong n dòng tiếp theo chứa hai số nguyên r1i và r2i (1≤r1i,r2i≤n) là thứ hạng của thí sinh thứ i ở vòng 1 và vòng 2. Các thứ hạng trong cùng một vòng đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên là số cách chọn. Dữ liệu đảm bảo đáp án không vượt quá 263.

Ràng buộc

  • 1≤n≤105, 1≤k≤10.
  • 1≤r1i,r2i≤n; các r1i đôi một khác nhau, các r2i đôi một khác nhau.
  • Đáp án không vượt quá 263.

Ví dụ

Input Output Giải thích
5 3
2 2
1 1
3 3
5 4
4 5
7 Có 10 cách chọn 3 thí sinh; chỉ 3 cách chọn có cả hai thí sinh cuối (hạng (5,4) và (4,5), không so sánh được) là không hợp lệ.
3 2
1 1
2 3
3 2
2 Thí sinh 1 hơn hai thí sinh còn lại; thí sinh 2 và 3 không so sánh được.

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