WATERJUG - Bình nước
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: adminchg

Công ty TNHH MTV nước XYZ chuyên sản xuất nước lọc đóng bình. Có N bình đựng nước đặt liên tiếp nhau, được đánh số từ 1 đến N. Mỗi bình có dung tích là ai lít. Tại mỗi bình đều có một vòi nước chảy với lưu lượng giống nhau là K lít/giây. Khi bình thứ i đầy nước (1 ≤ i < N) thì nước từ vòi tại bình i sẽ chảy qua bình i + 1. Khi bình thứ N đầy nước thì nước sẽ chảy ra ngoài.

Yêu cầu:

- Tìm số nguyên tương ứng với thời gian sớm nhất để bình thứ N đầy nước.

- Tìm số nguyên tương ứng với thời gian sớm nhất để tất cả các bình đầy nước.

Lưu ý: chỉ cần tìm ra thời gian nguyên sớm nhất (ví dụ như thời gian tìm được là 1.33 thì kết quả in ra sẽ là 2).

Dữ liệu

- Dòng đầu tiên chứa số nguyên dương NK.

- Dòng tiếp theo chứa N số nguyên không âm a1, a2,..., aN.

Kết quả: Ghi ra hai số nguyên không âm lần lượt là thời gian sớm nhất để bình thứ N đầy nước và thời gian sớm nhất để tất cả các bình đầy nước.

Hai số trên cùng một dòng cách nhau một dấu cách.

Ví dụ

WATERJUG.INP

WATERJUG.OUT

 4 2

 1 2 3 4

 2 2

 4 3

 10 7 3 2

 1 4

Giải thích:

- Test 01: Kết quả tìm được lần lượt là 1.25 và 1.25 nên in ra hai giá trị nguyên sớm nhất là 2 và 2.

- Test 02, kết quả tìm được lần lượt là 0.6667 và 3.3333 nên in ra hai giá trị nguyên sớm nhất là 1 và 4.

Giới hạn:

* 1 ≤ N ≤ 105.

* 1 ≤ K ≤ 109.

* 1 ≤ ai ≤ 109, với mọi 1 ≤ i ≤ N.

Back to Top