Que gần tốt
Đề bài
Mô tả
Bạn được cho chiếc que có độ dài nguyên dương .
Với mỗi chiếc que, bạn có thể đổi độ dài của nó thành một số nguyên dương bất kỳ (kéo dài ra hoặc rút ngắn lại). Chi phí để đổi độ dài một chiếc que từ thành là .
Độ dài được gọi là gần tốt với số nguyên nếu .
Hãy đổi độ dài của một số chiếc que (có thể là tất cả, cũng có thể không đổi cái nào) sao cho tồn tại một số nguyên dương mà mọi chiếc que đều gần tốt với , đồng thời tổng chi phí là nhỏ nhất có thể. Giá trị không được cho trước, bạn được tự chọn là số nguyên dương bất kỳ.
Nếu có nhiều giá trị cùng cho tổng chi phí nhỏ nhất, in ra giá trị nào cũng được.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên : số chiếc que.
- Dòng thứ hai chứa số nguyên : độ dài của các chiếc que.
Dữ liệu ra
In ra một dòng gồm hai số nguyên cách nhau bởi dấu cách: giá trị và tổng chi phí nhỏ nhất tương ứng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 10 1 4 |
3 7 | Đổi que dài 1 thành 2 và que dài 10 thành 4, chi phí . Bộ độ dài thu được đều gần tốt với . |
| 5 1 1 2 2 3 |
2 0 | Các độ dài đã gần tốt với sẵn rồi, không cần đổi gì nên chi phí bằng . |
| 4 1 1 5 5 |
2 4 | Với , hai que dài cần rút về , mỗi que tốn , tổng là . Chọn cũng cho tổng chi phí (mỗi que dài kéo lên , mỗi que dài rút về ), nên in nào trong hai giá trị đó cũng được chấp nhận. |
Bình luận