Một nhà máy có n máy có thế được sử dụng để tạo ra sản phẩm. Mục tiêu của bạn là tạo ra tổng số sản phẩm. Đối với mỗi máy, bạn biết số giây nó cần để tạo ra một sản phẩm. Các máy có thể hoạt động đồng thời và bạn có thể tự do quyết định lịch trình của chúng. Thời gian ngân nhất căn thiết để làm ra t sản phẩm là bao nhiêu?

Định dạng đầu vào: Dòng nhập đầu tiên có hai số nguyên n và t: số lượng máy móc và sản phẩm. Dòng tiếp theo ghi n số nguyên k1, k2,..., kn: thời gian cần thiết để tạo ra một sản phẩm sử dụng mỗi máy.

Ràng buộc: 1 <= n <= 2.10^5; 1 <= t <= 10^9; 1 <= ki <= 10^9;

Định dạng đầu ra: In một số nguyên: thời gian tối thiểu cần thiết để tạo ra t sản phẩm.

Input:

3 7
3 2 5

Output:

8

Giải thích: Trong 8s, máy 1 làm được 2 sản phẩm, máy 2 làm được 4 sản phẩm, máy 3 làm được 1 sản phẩm.

Một dãy số được gọi là dạng đỉnh núi nếu nó tăng dần đến một vị trí rồi giảm dần. Hãy tìm chỉ số của phần tử lớn nhất (đỉnh núi) trong dãy. (Dữ liệu đảm bảo dãy có dạng đỉnh núi).

Dữ liệu vào:

Dòng 1: N.

Dòng 2: Dãy số.

Dữ liệu ra:

Chỉ số của đỉnh (tính từ 1).

Ràng buộc:

3 <= N <= 10^5

Ví dụ:

Input:

5 
1 3 5 4 2

Output:

3

Có N cái chuồng nằm trên một đường thẳng tại các vị trí x1, x2, ..., xN. Cần xếp C con bò vào các chuồng sao cho khoảng cách nhỏ nhất giữa 2 con bò bất kỳ là lớn nhất có thể.

Dữ liệu vào:

Dòng 1: N và C.

Dòng 2: N vị trí của các chuồng (chưa chắc đã sắp xếp).

Dữ liệu ra:

Khoảng cách lớn nhất tìm được.

Ràng buộc:

2 <= C <= N <= 10^5

0 <= xi <= 10^9

Ví dụ:

Input:

5 3 
1 2 8 4 9

Output:

3

Cho một dãy số gồm N phần tử là một cấp số cộng (tăng dần) nhưng bị thiếu mất đúng 1 số. Hãy tìm số đó. (Gợi ý: Dùng tìm kiếm nhị phân dựa trên sự chênh lệch giữa giá trị thực tế và giá trị kỳ vọng).

Dữ liệu vào:

Dòng 1: N (Số lượng phần tử hiện có).

Dòng 2: Dãy số.

Dữ liệu ra:

Số bị thiếu.

Ràng buộc:

2 <= N <= 10^5

Ví dụ:

Input:

4 
2 4 8 10

Output:

6

Cho một bảng số kích thước NxN, trong đó phần tử ở hàng i, cột j có giá trị là i * j. Hãy tìm số nhỏ thứ K trong bảng này nếu ta trải phẳng bảng ra và sắp xếp lại.

Dữ liệu vào:

Hai số N và K.

Dữ liệu ra:

Số nhỏ thứ K.

Ràng buộc:

1 <= N <= 10^5

1 <= K <= N*N

Ví dụ:

Input:

3 7

Output:

6

Bạn có số tiền M. Có N cuốn sách với giá A[1], A[2],... Bạn muốn mua nhiều cuốn sách nhất có thể sao cho tổng giá tiền không vượt quá M. (Lưu ý: Dãy A chưa sắp xếp, bạn cần sắp xếp rồi dùng Tiền tố hoặc Binary Search, nhưng bài này ta dùng Binary Search trên kết quả số lượng sách K). Dữ liệu vào:

Dòng 1: N và M.

Dòng 2: Giá các cuốn sách.

Dữ liệu ra:

Số lượng sách tối đa mua được.

Ràng buộc:

1 <= N <= 10^5

1 <= M <= 10^14

Ví dụ:

Input:

5 10 
2 4 3 5 1

Output:

4

Có N cái cây. Mỗi ngày, một cái cây sẽ tự lớn thêm 1cm. Bạn có thể dùng thuốc tăng trưởng để làm 1 cái cây bất kỳ lớn thêm K cm ngay lập tức (mỗi ngày chỉ dùng thuốc 1 lần). Bạn muốn tất cả các cây đều đạt chiều cao tối thiểu là H. Hỏi sau ít nhất bao nhiêu ngày thì đạt được mục đích? (Giả sử ban đầu các cây cao 0). Lưu ý: Bài này hơi khó, ta đổi sang bài đơn giản hơn: Bài Toán Bơm Bóng Tên bài thay thế: Bơm Bóng Bay Mô tả: Có N quả bóng. Bạn cần bơm sao cho quả bóng nhỏ nhất có kích thước càng lớn càng tốt sau M lần bơm thêm (mỗi lần bơm tăng 1 đơn vị cho 1 quả). -> Binary Search kết quả kích thước tối thiểu.

Dữ liệu vào:

N và M.

Kích thước ban đầu của N quả bóng.

Dữ liệu ra:

Kích thước nhỏ nhất tối đa có thể đạt được.

Ràng buộc:

N, M <= 10^5

Ví dụ:

Input:

3 4 
2 4 6

Output:

5

Cho dãy A đã sắp xếp tăng dần. Hãy đếm xem số X xuất hiện bao nhiêu lần trong dãy.

Dữ liệu vào:

Dòng 1: N và X.

Dòng 2: N số nguyên dãy A.

Dữ liệu ra:

Số lần xuất hiện của X.

Ràng buộc:

1 <= N <= 10^5

|A[i]|, |X| <= 10^9

Ví dụ:

Input:

7 2 
1 1 2 2 2 3 4

Output:

3