| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT015F - ACM PTIT 2015 F - Quản lý kho |
Công ty XYZ có n kho và m nhân viên làm nhiệm vụ quản lý các kho. Cho biết các thông tin sau:
- Nhân viên thứ i có năng lực P[i] (1 <= P[i] <= 10^6);
- Các kho đều giống nhau và mỗi kho chỉ do một nhân viên quản lý, nhưng một nhân viên có thể quản lý nhiều kho. Nếu nhân viên thứ i quản lý k kho thì độ an toàn của các kho đó là S = [P[i]/k] (phần nguyên của phép chia P[i]/k). Nếu một kho không có ai quản lý thì độ an toàn bằng 0;
- Độ an toàn của tất cả các kho là L bằng độ an toàn nhỏ nhất trong n kho;
- Mỗi tháng công ty sẽ trả lương cho các nhân viên, nếu nhân viên i được chọn thì sẽ phải trả P[i] dollar. Tổng số tiền phải trả cho các nhân viên được chọn là Y.
Yêu cầu: Chọn và phân công các nhân viên quản lý các kho để độ an toàn của tất cả các kho (L) là lớn nhất, nếu có nhiều cách phân công thì chọn các hết ít tiền nhất (Y).
Input
Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Mỗi bộ dữ liệu có cấu trúc như sau:
- Dòng thứ nhất ghi hai số nguyên dương gồm 2 số n, m (1 <= n, m <= 300).
- Dòng thứ hai chứa gồm m số P[i].
Kết thúc file là m = n = 0.
Output
Với mỗi bộ dữ liệu, ghi ra trên một dòng gồm 2 số L và Y là kết quả tương ứng với bộ dữ liệu trong dữ liệu vào.
Example
Input: 2 1
7
1 2
10 9
2 5
10 8 6 4 1
5 4
1 1 1 1
0 0 Output: 3 7
10 10
8 18
0 0
| Được gửi lên bởi: | adm |
| Ngày: | 2015-04-19 |
| Thời gian chạy: | 3s |
| 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 KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
