trang chủ / đề bài / icpc21_mb_k

Ma trận từ điển

Đề bài

Mô tả

Một ma trận hoán vị (Lex Matrix) là một ma trận kích thước m×n gồm m hàng và n cột. Các hàng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ax,y là giá trị thứ y trên hàng x. Mỗi hàng là một hoán vị của 1,2,…,n.

Ma trận A được coi là lớn hơn ma trận B nếu khi so sánh lần lượt từng ô, bắt đầu từ hàng đầu tiên, từ trái sang phải rồi sang hàng tiếp theo, và cứ thế, thì tại cặp ô (i,j) đầu tiên mà Ai,j≠Bi,j ta có Ai,j>Bi,j.

Cho ma trận A. Bạn được phép chọn 2 hàng hoặc 2 cột rồi đổi chỗ chúng, và lặp lại thao tác này bao nhiêu lần tùy ý, để biến A thành ma trận lớn nhất có thể. Gọi ma trận lớn nhất này là A′. Cho q cặp số xi và yi (1≤xi≤m, 1≤yi≤n), hãy tìm giá trị Axi,yi′.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên m và n (1≤m,n≤500).
  • m dòng tiếp theo mô tả ma trận A, mỗi dòng gồm n số là một hoán vị của 1,2,…,n.
  • Dòng tiếp theo chứa số nguyên q (1≤q≤10000).
  • q dòng tiếp theo, mỗi dòng chứa hai số nguyên xi và yi (1≤xi≤m, 1≤yi≤n).

Dữ liệu ra

In ra q dòng, dòng thứ i chứa giá trị Axi,yi′.

Ràng buộc

  • 1≤m,n≤500.
  • Mỗi hàng của A là một hoán vị của 1,2,…,n.
  • 1≤q≤10000, 1≤xi≤m, 1≤yi≤n.

Ví dụ

Input Output Giải thích
2 3
1 2 3
1 2 3
2
1 1
2 3
3
1
Đảo ngược thứ tự các cột, cả hai hàng đều thành 3,2,1.
3 3
2 1 3
3 1 2
1 3 2
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
3
2
1
2
3
1
2
1
3
Ví dụ bổ sung (không có trong đề gốc). Ma trận lớn nhất là (321231213): giữ hàng 1 ở đầu, sắp các cột theo thứ tự 3,1,2, rồi xếp các hàng còn lại giảm dần.

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