trang chủ / đề bài / icpc22_mb_l

Sắp xếp bảng

Đề bài

Mô tả

Cho bảng A gồm m hàng và n cột. Mỗi ô của bảng chứa một số nguyên có giá trị tuyệt đối không vượt quá 100. Bạn có thể áp dụng phép toán sort(k): sắp xếp các hàng của bảng theo thứ tự tăng dần của giá trị ở cột thứ k. Nếu có nhiều hàng có cùng giá trị ở cột thứ k thì thứ tự tương đối giữa các hàng đó không thay đổi.

Cho bảng B được tạo thành bằng cách áp dụng lần lượt dãy phép toán sort(k1), sort(k2), ..., sort(ks) lên bảng A. Hãy tìm dãy phép toán ngắn nhất mà khi áp dụng lên bảng A cũng cho ra bảng B.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên m, n và s (1≤m≤20, 1≤n≤9, 1≤s≤100).

m dòng tiếp theo, mỗi dòng chứa n số nguyên là các ô của bảng A.

Dòng tiếp theo chứa s số nguyên k1,k2,…,ks (1≤ki≤n) là một dãy phép toán khi áp dụng lên bảng A cho ra bảng B.

Dữ liệu ra

Dòng đầu tiên in ra độ dài của dãy phép toán ngắn nhất cho ra bảng B. Dòng tiếp theo in ra dãy phép toán đó (để trống nếu độ dài bằng 0). Nếu có nhiều dãy cùng độ dài, in ra dãy nhỏ nhất theo thứ tự từ điển.

Ràng buộc

  • 1≤m≤20, 1≤n≤9, 1≤s≤100.
  • Mỗi ô của bảng có giá trị tuyệt đối không vượt quá 100.
  • 1≤ki≤n.

Ví dụ

Input Output Giải thích
2 2 4
1 2
2 1
1 2 1 2
1
2
Bảng B gồm hai hàng 2 1 rồi 1 2, chính là kết quả của một phép sort(2).
4 3 2
1 5 2
1 3 7
2 0 0
3 9 9
1 1
0

Bảng A đã được sắp xếp theo cột 1 nên B=A, dãy rỗng là đủ (dòng thứ hai để trố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