Bob là 1 thợ mộc tài hoa. Hiện tại anh đang có kế hoạch xáy dựng một căn nhà toàn bộ bằng gỗ. Căn nhà được xây bởi các khúc gỗ khác nhau và tổng độ dài của các thanh gỗ là L. Để lấy các khúc gỗ đó, anh ấy cần vào rừng và chặt cây. Khu rừng gần chỗ anh có N cây với độ cao khác nhau. Bob sẽ dùng một cái máy cưa đặc biệt, nó có thể cắt một lượt qua tất cả các cây.

Đầu tiên, anh ấy sẽ chọn một độ cao cố định là H, sau đó dùng máy cưa đặc biệt để cắt một đường theo độ cao H này trên các cây có độ cao lớn H.

Ví dụ: Các cây có độ cao lần lượt là: 10, 16, 17, 15. Chọn H bằng = 15. Do đó, cây thứ 2, 3 sẽ được cắt và tổng độ dài các khúc gỗ thu được là 1 + 2 = 3.

Cho độ cao của các cây trong rừng và giá trị L. (Tổng độ dài của các khúc gỗ cần). Hãy giúp Bob tìm giá trị lớn nhất của H thòa mãn rằng Bob chỉ cần dùng máy cắt đúng một lượt để thu được số các khúc gỗ căn thiết.

Chú ý: Tổng độ dài các khúc gõ có thóa măn có thể lớn hơn L (hay nói cách khác L ≤ tổng độ dài).

Đầu vào:

Dòng đầu tiên chứa một số nguyên mô tả số lượng cây N (1 < N ≤ 10^6) và L tổng độ dài của các khúc gỗ cần dùng (1 ≤ L ≤ 2 * 10^9)

Dòng tiếp theo là độ cao tương ứng của các cây h[i]. (h[i] < 10^9). Tổng độ cao của các cây lớn hơn hoặc bằng L.

Đầu ra:

Dòng duy nhất gồm 1 số nguyên duy nhất: giá trị độ cao lớn nhất mà tại đó Bob cắt đúng một đường đề thu được các khúc gỗ thoa mãn.

Input 01:

3 6
1 2 3

Output 01:

0

Input 02:

4 10
10 15 12 13

Output 02:

10

Input 03:

4 1
5 5 5 5

Output 03:

4

Cho số nguyên dương N rất lớn. Hãy tìm số nguyên dương K lớn nhất sao cho K * K <= N. (Không dùng hàm sqrt có sẵn, hãy dùng tìm kiếm nhị phân).

Dữ liệu vào:

Một số nguyên dương N.

Dữ liệu ra:

Số nguyên K.

Ràng buộc:

1 <= N <= 10^18

Ví dụ:

Input:

10

Output:

3

Có N túi kẹo, túi thứ i có A[i] viên kẹo. Cần chia các túi này cho K em bé sao cho mỗi em bé nhận được một số túi kẹo LIÊN TIẾP nhau. Hãy chia sao cho tổng số kẹo lớn nhất mà một em bé nhận được là nhỏ nhất có thể (Tối thiểu hóa cái tối đa).

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Số kẹo trong các túi. Dữ liệu ra:

Tổng số kẹo lớn nhất tối thiểu. Ràng buộc:

1 <= K <= N <= 10^5

A[i] <= 10^9

Ví dụ:

Input:

5 3 
2 4 7 3 5

Output:

8

Có N máy sản xuất. Máy thứ i cần T[i] giây để tạo ra 1 sản phẩm. Các máy hoạt động song song. Hỏi cần ít nhất bao nhiêu giây để tạo ra tổng cộng K sản phẩm?

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Thời gian T[i] của các máy.

Dữ liệu ra:

Thời gian ít nhất.

Ràng buộc:

1 <= N <= 10^5

1 <= K <= 10^9

1 <= T[i] <= 10^9

Ví dụ:

Input:

3 7 
3 2 5

Output:

8

Cho dãy A gồm N phần tử đã sắp xếp tăng dần và số nguyên K. Hãy đếm số cặp (i, j) sao cho i < j và A[i] + A[j] = K. (Sử dụng tìm kiếm nhị phân cho mỗi A[i]).

Dữ liệu vào:

Dòng 1: N và K.

Dòng 2: Dãy A.

Dữ liệu ra:

Số lượng cặp thỏa mãn.

Ràng buộc:

1 <= N <= 10^5

|A[i]| <= 10^9

Ví dụ:

Input:

5 9 
1 3 5 6 8

Output:

2

Có n sợi dây, bạn cần cắt k đoạn dây có cùng chiều dài từ chúng. Tìm chiều dài tối đa của các mảnh dây bạn có thể nhận được.

Đầu vào: Dòng đầu tiên chứa hai số nguyên n và k. N dòng tiếp theo mỗi dòng ghi một số, chiều dài của sợi dây là a(i].

Ràng buộc: (1 <= n, k <= 10000); (1 <= ai ≤ 10^7)

Đầu ra: In ra chiều dài của mảnh dây dài nhất mà bạn có thể cắt với 6 số sau dấu phẩy.

Input:

4 11
802 743 457 539

Output:

200.500000

Kì thì cuối kì môn Triết ở trường đại học xyz sáp diễn ra. Tèo và bạn bè có ý định sẽ photo phao thi để bán kiếm tiền, hiện tại Tèo và bạn của mình đã có bản gốc của phao thi. Theo ước tính của Tèo thì có n bạn sẽ mua phao thi của Tèo. Tèo không có ý định bán bản phao gốc của minh nên sẽ đi photo n bản nữa để bán, tới quán photo chỉ còn 2 máy photo có thể hoạt động. Trong đó máy photo 1 cần x giây để photo xong phao thi cho Tèo, máy thứ 2 căn y giây. Vì muốn nhanh chóng đem phao đi bán nên Tèo muốn nhờ bạn tính hộ là anh ãy cần ít nhất bao nhiêu giây để có thể photo ra n bản khác từ 1 bản gốc ban đầu. Chú ý các máy photo có thể photo từ bán gốc hoặc có thể photo từ bản đã sao đã được in từ bản gốc. 2 máy này có thể hoạt động một cách đông thời.

Đầu vào: 1 dòng chứa ba số nguyên n, x và y;

Ràng buộc: (1 <= n <= 2*10^8, 1 <= x, y <= 10).

Đầu ra: In ra thời gian tối thiếu mà Tèo cần.

Input:

5 1 2

Output:

4

Giải thích: Tèo cần photo 5 bản, ban đầu Tèo dùng máy số 1 để photo ra ban sao đầu tiên. Sau đó còn lại 3 giây, Tèo photo được 3 bản từ máy 1 và 1 bản từ máy 2. Vậy là đủ 5 bản.

Bạn được cung cấp một mảng chứa n số nguyên dương. Nhiệm vụ của bạn là chia mảng thành k mảng con liên tiếp sao cho tổng lớn nhất trong một mảng con càng nhỏ càng tốt. (Gợi ý sử dụng binary search on answer. Binary search trên tổng lớn nhất của 1 mảng con)

Đầu vào: Dòng đầu tiên chứa hai số nguyên n và k: kích thước của máng và số máng con trong phép chia. Dòng tiếp theo chứa n số nguyên x1, x2,..., xn: nội dung của mẳng.

Ràng buộc: 1 <= n <= 2*10^5; 1 <= k <= n; 1 <= xi <= 10^9;

Đầu ra: In một số nguyên: tổng lớn nhất trong một mảng con trong phép chia tối ưu.

Input:

5 3
4 2 7 3 5

Output:

8