trang chủ / đề bài / icpc23_nat_g

Tổ hợp xe bảo vệ

Đề bài

Mô tả

Cờ vua là một trò chơi chiến thuật đã có từ nhiều thế kỷ. Hai người chơi lần lượt di chuyển các quân cờ của mình trên một bàn cờ dạng lưới vuông. Mục tiêu của trò chơi là bắt vua của đối phương vào thế không thể thoát, gọi là "chiếu hết". Một trong sáu loại quân cờ là quân xe. Quân xe là một quân mạnh, có thể di chuyển theo hàng ngang hoặc hàng dọc bao nhiêu ô cũng được, miễn là không có vật cản trên đường đi. Quân xe thường được biểu diễn bằng hình một tòa tháp và được coi là một trong những quân giá trị nhất nhờ khả năng kiểm soát nhiều đường và đóng góp vào nhiều chiến thuật khác nhau.

Là một người đam mê cờ vua, MofK luôn dành thời gian nghiên cứu các quân cờ, thế cờ, chiến lược chơi, rồi đưa ra những nhận định riêng để sử dụng khi đấu với các Đại kiện tướng ở những giải đấu lớn. Hôm nay, MofK quyết định dành trọn một ngày để nghiên cứu tính chất của quân xe. MofK có nhiều bàn cờ và bộ cờ, nên quyết định nghiên cứu trên bàn cờ n×n thay vì bàn cờ 8×8. Mỗi ô trên bàn cờ có thể đặt nhiều nhất một quân xe. Ban đầu, MofK đã đặt một số quân xe lên một số ô của bàn cờ. Càng đặt nhiều quân xe, MofK càng thấy nhiều cặp xe bảo vệ nhau trong thế cờ. Để nâng cao khả năng dự đoán, MofK muốn đặt thêm đúng k quân xe lên bàn cờ sao cho có đúng p cặp xe bảo vệ nhau.

Hai quân xe khác nhau trên bàn cờ được gọi là bảo vệ nhau nếu:

  • hai quân xe nằm trên cùng một hàng hoặc cùng một cột của bàn cờ, và
  • không có quân xe nào khác nằm giữa hai quân xe đó.

Cho bàn cờ ban đầu cùng hai số k và p, hãy giúp MofK tìm cách đặt thêm đúng k quân xe lên bàn cờ sao cho có đúng p cặp xe bảo vệ nhau, hoặc cho biết không có cách nào làm được điều đó.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng:

  • Dòng đầu tiên chứa ba số nguyên n, k và p (1≤n≤103, 0≤k≤106, 0≤p≤109), lần lượt là kích thước bàn cờ, số quân xe cần đặt thêm và số cặp xe bảo vệ nhau cần có trên bàn cờ.
  • n dòng tiếp theo mô tả bàn cờ ban đầu, mỗi dòng chứa một xâu độ dài n. Mỗi ký tự của mỗi xâu là R (ô có quân xe) hoặc . (ô không có quân xe).

Dữ liệu vào kết thúc bởi một dòng chứa ba số 0, dòng này không phải là một bộ dữ liệu.

Dữ liệu bảo đảm tổng n2 của tất cả các bộ dữ liệu không vượt quá 20002.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu không có cách đặt thêm đúng k quân xe lên bàn cờ sao cho có đúng p cặp xe bảo vệ nhau, in ra một dòng NO.

Ngược lại, in ra YES ở dòng đầu tiên. n dòng tiếp theo mô tả bàn cờ sau khi đặt thêm quân xe theo cùng định dạng với dữ liệu vào: mỗi dòng chứa một xâu độ dài n, mỗi ký tự là R (ô có quân xe) hoặc . (ô không có quân xe).

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

Ràng buộc

  • 1≤n≤103, 0≤k≤106, 0≤p≤109
  • Tổng n2 của tất cả các bộ dữ liệu không vượt quá 20002.

Ví dụ

Input Output Giải thích
7 4 12
.......
.R...R.
.......
...R...
.......
.R...R.
.......
7 0 12
.......
.R...R.
.......
...R...
.......
.R...R.
.......
10 22 136
.RR.RR.RR.
.RRRRRRRR.
.R......R.
..RRRRRR..
..R....R..
..R....R..
.RRRRRRRR.
R........R
RRRRRRRRRR
RRRRRRRRRR
0 0 0
YES
.......
.R.R.R.
.......
.R.R.R.
.......
.R.R.R.
.......
NO
YES
.RR.RR.RR.
.RRRRRRRR.
.RRRRRRRR.
..RRRRRR..
..RRRRRR..
..RRRRRR..
.RRRRRRRR.
RRRRRRRRRR
RRRRRRRRRR
RRRRRRRRRR
Bộ thứ nhất: sau khi đặt thêm 4 quân xe, 9 quân xe tạo thành lưới 3×3, mỗi hàng và mỗi cột có 2 cặp bảo vệ nhau, tổng cộng 12 cặp. Bộ thứ hai: không được đặt thêm quân nào (k=0), nhưng ban đầu chỉ có 4 cặp xe bảo vệ nhau, nên không thể có đúng p=12 cặp.
1 1 0
.
2 2 1
..
..
2 1 2
R.
..
3 3 0
...
...
...
0 0 0
YES
R
YES
RR
..
NO
YES
R..
.R.
..R
Ví dụ bổ sung. Bộ thứ ba: hai quân xe chỉ tạo được nhiều nhất 1 cặp bảo vệ nhau. Bộ thứ tư: ba quân xe trên đường chéo không bảo vệ nhau.

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