trang chủ / đề bài / icpc19_reg_l

Hình vuông Latin

Đề bài

Mô tả

Hình vuông Latin là một bảng n×n được điền n số nguyên từ 1 đến n sao cho mỗi số xuất hiện đúng một lần trên mỗi hàng và trên mỗi cột.

Ví dụ, sau đây là một hình vuông Latin:

1 2 3
2 3 1
3 1 2

Gon rất thích hình vuông Latin và đang tạo một hình vuông như vậy.

Đầu tiên Gon tạo một bảng trống gồm n hàng và n cột. Sau đó Gon viết k·n số vào bảng, dùng k số khác nhau, mỗi số xuất hiện đúng n lần, sao cho trên mỗi hàng và mỗi cột không có số nào xuất hiện quá một lần.

Tuy nhiên, Gon không biết phải làm tiếp như thế nào. Hãy giúp Gon điền nốt hình vuông Latin. Tất nhiên, bạn không được xóa số nào Gon đã viết, tức là bạn chỉ được viết vào các ô trống.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và k (1≤n≤100, 0≤k≤n).

Mỗi dòng trong n dòng tiếp theo chứa n số nguyên mô tả bảng. Các số nằm trong đoạn từ 0 đến n, trong đó 0 là ô trống.

Dữ liệu đảm bảo trên mỗi hàng và mỗi cột không có hai ô nào cùng giá trị dương, và trong bảng có đúng k số dương khác nhau, mỗi số xuất hiện đúng n lần.

Dữ liệu ra

Nếu không có lời giải, in ra đúng một dòng NO.

Ngược lại, in ra YES, sau đó là n dòng, mỗi dòng chứa n số: hình vuông Latin đã điền đầy đủ.

Nếu có nhiều lời giải, in ra một lời giải bất kỳ.

Ràng buộc

  • 1≤n≤100, 0≤k≤n.
  • Bảng có đúng k giá trị dương khác nhau, mỗi giá trị xuất hiện n lần, không giá trị nào lặp lại trên một hàng hay một cột.

Ví dụ

Input Output Giải thích
3 1
2 0 0
0 2 0
0 0 2
YES
2 1 3
3 2 1
1 3 2
Số 2 đã nằm trên đường chéo chính. Các số 1 và 3 được điền vào các ô trống sao cho mỗi hàng và mỗi cột có đủ 1,2,3.
2 0
0 0
0 0
YES
1 2
2 1
Ví dụ bổ sung (không có trong đề gốc). Bảng trống, điền một hình vuông Latin bất kỳ.

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