TRÒ CHƠI LAWRENCE

Nguồn: kc97blf
Trong lúc rảnh rỗi, Nguyên đã làm được một trò chơi là Lawrence. Trò chơi này gồm n trạm, các trạm được đánh số từ 1 đến n. Mỗi trạm được gán một giá trị gọi là giá trị chiến thuật. Các trạm được nối với nhau bởi n-1 đường ray hai chiều, đường ray thứ i nối trạm i và i+1 với nhau. Nguyên định nghĩa giá trị chiến thuật của toàn bộ các trạm là tổng các tích của chiến thuật của các cặp trạm được nối trực tiếp hoặc gián tiếp với nhau. Ví dụ với 4 trạm như hình dưới đây:

Giá trị chiến thuật của toàn bộ các trạm là 4×5+4×1+4×2+5×1+5×2+1×2=49

Trong trò chơi này, hệ thống có nhiệm vụ chọn số trạm n trong trò chơi, số lượt đánh bom m của người chơi và gán giá trị chiến thuật cho từng trạm. Ở mỗi lượt đánh bom, người chơi được quyền loại bỏ một đường ray trong trò chơi. Người chơi sẽ thắng nếu đánh bom một cách tối ưu sao cho giá trị chiến thuật của toàn bộ các trạm là nhỏ nhất cho thể trong thời gian 30 giây. Nếu người chơi không đưa ra được cách đánh bom tối ưu, máy sẽ dành chiến thắng.

Ví dụ với 4 trạm như trên và số lượt đánh bom m là 1, nếu người chơi chọn đánh bom đường ray thứ 2:

Giá trị chiến thuật của toàn bộ các trạm còn lại là 4×5+1×2=22. Tuy vậy, nếu người chơi chọn đánh bom đường ray đầu tiên:

Giá trị chiến thuậ của toàn bộ các trạm còn 5×1+5×2+1×2=17. Đây là cách đánh bom tối ưu vì thế người chơi sẽ chiến thắng.

Để tránh hiện tượng giật, lag, hệ thống phải tự tính toán được giá trị chiến thuật nhỏ nhất của toàn bộ các trạm trong mỗi trò chơi trong vòng 1 giây. Hãy giúp Nguyên viết chương trình làm nhiệm vụ này để anh có thể nhanh chóng hoàn thiện trò chơi của mình.

Dữ liệu vào: Từ tệp văn bản LAWRENCE.INP

+ Dòng đầu tiên ghi 2 số nguyên n và m (1≤n≤500, 0≤m<n). n là số trạm trong trò chơi và m là số lượt đánh bom của người chơi.

+ Dòng thứ 2 chứa n số nguyên có giá trị trong đoạn từ 1 đến 5, số thứ i là giá trị chiến thuật của trạm thứ i.

Kết quả: Ghi vào tệp văn bản LAWRENCE.OUT một số nguyên duy nhất là giá trị chiến thuật nhỏ nhất của toàn bộ trạm.

Ví dụ:

LAWRENCE.INP	LAWRENCE.OUT		LAWRENCE.INP	LAWRENCE.OUT
4 1 4 5 1 2	17		4 2 4 5 1 2	2

Test - code - đề - solution
back