| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT127H - Tấn công đường ray |
Giữa những kho chứa (được gán trọng số từ 1 đến 5) có các đường ray nối. Giá trị chiến lược trên một đường ray được tính bằng tổng tất cả giá trị của các đoạn cộng lại. Ví dụ với đường ray được mô tả như sau:
Thì giá trị chiến lược sẽ là: 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.
Giả sử người ta muốn tấn công một đoạn đường ray sao cho giá trị chiến lược còn lại là nhỏ nhất. Trong trường hợp trên nếu tấn công đoạn từ 5 đến 1
thì giá trị chiến lược sẽ là: 4*5 + 1*2 = 22. Còn nếu tấn công đoạn 4 đến 5:
thì giá trị sẽ chỉ là: 5*1 + 5*2 + 1*2 = 17. Đây là giá trị nhỏ nhất có thể.
Input
Gồm nhiều bộ test, mỗi bộ test gồm hai số nguyên N và M (1<=N<=500 và 0<=M<n) trong đó N là số kho chứa trên đường ray và M là số lần tấn công. Dòng tiếp theo là N số nguyên dương từ 1 đến 5 theo thứ tự là trọng số các kho chứa trên đường.
Dữ liệu vào kết thúc với một dòng chứa 2 số 0.
Output
ghi trên một dòng số nguyên dương là giá trị chiến lược nhỏ nhất có thể còn lại.
Example
Input:4 1
4 5 1 2
4 2
4 5 1 2
0 0
Output:17
2
| Được gửi lên bởi: | adm |
| Ngày: | 2012-03-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2024-02-07 13:30:33
non Last edit: 2024-02-07 13:37:08 |
|
|
2024-02-07 13:30:23
E Last edit: 2024-02-07 13:33:20 |
|
|
2014-10-09 08:57:12 Black Hole
n^3 mãi mới AC,time chặt thật :3 |
