YUGI - Yugi-Oh
Giới hạn- Thời gian: 0.1s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Các bạn đã đọc bộ truyện tranh Nhật Bản Yugi-oh chắc hẳn ai cũng cực kì yêu thích trò chơi bài Magic. Bộ bài và chiến thuật chơi quyết định đến sự thắng thua của đối thủ(mà sự thắng thua thì còn liên quan đến cả tính mạng >_<). Vì thế tầm quan trọng của bộ bài là rất lớn. Một bộ bài tốt không chỉ bao gồm các quân bài mạnh mà còn phụ thuộc vào sự hỗ trợ tương tác giữa các quân bài. Bộ bài của Yugi là một bộ bài có sự bổ sung, hỗ trợ cho nhau rất tốt, điều này là 1 trong các nguyên nhân khiến Kaiba luôn là kẻ chiến bại.
Tình cờ Kaiba đã tìm được 1 quân bài ma thuật mà chức năng của nó là chia bộ bài hiện có của đối thủ ra làm K phần, mỗi phần có ít nhất 1 quân bài (điều này làm giảm sức mạnh của đối thủ). Kaiba quyết định áp dụng chiến thuật này với Yugi. Hiện tại Yugi có trong tay N quân bài, 2 quân bài i, j có sức mạnh tương tác a(i,j) (a(i,j) = a(j,i)). Kaiba muốn chia các quân bài thành K phần theo quy tắc sau:
- Giả sử K phần là P1, P2, ..., Pk thì độ giảm sức mạnh giữa 2 phần u,v là b(u,v) = min(a(i,j) với i thuộc Pu, j thuộc Pv).
- Độ giảm sức mạnh của bộ bài là S = min(b(u,v) với 1 ≤ u, v ≤ K).
Kaiba muốn chia K phần sao cho S lớn nhất
Input
- Dòng đầu là 2 số N,K(2 ≤ K ≤ N ≤ 200)
- N dòng tiếp theo mỗi dòng là N số a(i,j) (a(i,j) ≤ 32767; nếu i = j thì a(i,j) = 0)
Output
Gồm 1 dòng duy nhất là S lớn nhất
Example
Input: 4 3 0 1 2 3 1 0 2 3 2 2 0 3 3 3 3 0 Output: 2
- Người up: nghia
- Nguồn bài: Không rõ nguồn gốc