Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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:Admin
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 PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2019-01-21 04:07:19
có ai biết cách làm k
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.