PreVOI 2023 - Phú Thọ - Trò chơi trên bảng
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho bảng kích thước ~n \times n~ ~(3 \le n \le 10)~, các hàng của bảng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ban đầu, mỗi ô của bảng sẽ được đặt một quân bài, ô giao giữa hàng ~i~ ~(1 \le i \le n)~ và cột ~j~ ~(1 \le j \le n)~ đặt quân bài có số hiệu là ~(i-1) \cdot n+j~. Người quản trò sẽ thống nhất hai dãy số nguyên ~r_1, r_2, \dots, r_5~ và ~c_1, c_2, \dots, c_5~, rồi lấy ngẫu nhiên ~n^2-5~ quân bài khỏi bảng, như vậy trên bảng sẽ chỉ còn ~5~ quân bài. Trong ~n^2-5~ quân bài, người quản trò sẽ tiếp tục lấy ~m~ quân bất kì ~(0 < m \le n^2-5)~ và tráo ngẫu nhiên, sau đó xếp thành một dãy bài cho người chơi xem các lá bài này. Người chơi sẽ thực hiện ~m~ lượt chơi, mỗi lượt diễn ra như sau:
Người chơi chọn một quân bài trên bảng rồi bỏ đi (trên bảng sẽ còn lại ~4~ quân bài);
Người quản trò lấy quân bài ở đầu dãy bài, xếp quân bài này vào lại vị trí ban đầu trên bảng (ô trên bảng ban đầu chứa quân bài trước khi người quản trò lấy ra khỏi bảng), khi đó, trên bảng sẽ có ~5~ quân bài, dãy bài giảm đi một quân bài. Người quản trò sẽ tính điểm cho người chơi tại lượt này như sau: Gọi ~x~ là số quân bài nhiều nhất cùng hàng, ~y~ là số quân bài nhiều nhất cùng cột, khi đó điểm được tính bằng ~r_x+c_y~.
Yêu cầu: Hãy giúp người chơi đạt được tổng điểm nhiều nhất.
Input
Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(m \le 50)~;
Dòng thứ hai chứa ~10~ số nguyên ~r_1, r_2, \dots, r_5, c_1, c_2, \dots, c_5~, các số là số nguyên không âm và không vượt quá ~10^6~;
Dòng thứ ba chứa ~5~ số nguyên mô tả ~5~ quân bài còn lại trên bảng sau khi người quản trò lấy bài ra khỏi bảng;
Dòng thứ tư gồm ~m~ số mô tả dãy bài sau khi người quản trò tráo và xếp thành dãy.
Output
Ghi ra một số nguyên duy nhất là tổng điểm nhiều nhất.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~n = 3~; |
| 2 | ~30\%~ | ~n \le 6~; |
| 3 | ~20\%~ | ~n \le 7~; |
| 4 | ~20\%~ | ~n \le 10~. |
Sample Input 1
3 2
0 2 3 0 0 0 1 3 0 0
1 2 5 6 7
9 3
Sample Output 1
9
Notes

Bình luận