Có N kiện hàng nằm trên một băng chuyền, kiện thứ i có trọng lượng W[i]. Một con tàu cần vận chuyển hết số hàng này trong D chuyến. Các kiện hàng phải được chất lên tàu theo đúng thứ tự trên băng chuyền (không được đổi chỗ, phải cắt đoạn liên tiếp). Hãy tìm sức chứa tối thiểu của con tàu để có thể hoàn thành công việc trong đúng D ngày (hoặc ít hơn).

Dữ liệu vào:

Dòng 1: Hai số nguyên N và D (1 <= D <= N <= 10^5).

Dòng 2: N số nguyên W[i] (1 <= W[i] <= 500).

Dữ liệu ra:

Sức chứa tối thiểu của con tàu.

Ví dụ:

Input:

5 3 
1 2 3 4 5

Output:

6

Có N quyển sách với số trang lần lượt là P[1], P[2], ..., P[N]. Cần chia N quyển sách này cho K người chép sách sao cho các quyển sách được chia phải liên tiếp nhau. Mỗi người sẽ chép tổng số trang của các quyển sách mình được chia. Hãy chia sao cho số trang nhiều nhất mà một người phải chép là nhỏ nhất có thể.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= N <= 100000, 1 <= K <= N).

Dòng 2: N số nguyên P[i] (1 <= P[i] <= 10^9).

Dữ liệu ra:

Số trang lớn nhất tối thiểu.

Ví dụ:

Input:

4 2 
10 20 30 40

Output:

60

Để làm một chiếc bánh cần N loại nguyên liệu. Loại thứ i cần A[i] gram. Trong bếp hiện có B[i] gram nguyên liệu loại i. Bạn có K gram "bột thần kỳ", 1 gram bột thần kỳ có thể biến thành 1 gram nguyên liệu bất kỳ. Hỏi bạn có thể làm được tối đa bao nhiêu chiếc bánh?

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= N <= 10^5, 1 <= K <= 2*10^9).

Dòng 2: N số nguyên A[i] (1 <= A[i] <= 10^9).

Dòng 3: N số nguyên B[i] (1 <= B[i] <= 10^9).

Dữ liệu ra:

Số bánh tối đa.

Ví dụ:

Input:

3 1 
2 1 4 
11 3 16

Output:

4

Có N ngôi nhà nằm trên một trục tọa độ. Nhà thứ i ở vị trí X[i]. Bạn cần đặt K trạm phát sóng WiFi tại các vị trí bất kỳ (không nhất thiết phải tại vị trí nhà). Mỗi trạm có phạm vi phủ sóng là R (tức là nếu đặt tại P thì phủ sóng [P-R, P+R]). Hãy tìm giá trị R nhỏ nhất để tất cả các ngôi nhà đều có sóng WiFi. (Kết quả là số thực làm tròn 1 chữ số thập phân).

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= K <= N <= 10^5).

Dòng 2: N số nguyên X[i] (sắp xếp tăng dần) (0 <= X[i] <= 10^9).

Dữ liệu ra:

Giá trị R nhỏ nhất.

Ví dụ:

Input:

3 1 
1 3 5

Output:

2.0

Có N hình chữ nhật kích thước W[i] x H[i]. Bạn cần cắt từ các hình chữ nhật này ra ít nhất K hình vuông có cùng kích thước. Hãy tìm cạnh hình vuông lớn nhất có thể cắt được.

Dữ liệu vào:

Dòng 1: Hai số nguyên N và K (1 <= N <= 10^5, 1 <= K <= 10^9).

N dòng tiếp theo: Mỗi dòng chứa W[i] và H[i] (1 <= W[i], H[i] <= 10^9).

Dữ liệu ra:

Cạnh hình vuông lớn nhất.

Ví dụ:

Input:

2 10 
4 4 
5 5

Output:

1

Bạn đang ở ô (1, 1) và muốn đến ô (N, M). Tuy nhiên, có K quả bom rải rác trên bản đồ. Một ô được gọi là nguy hiểm nếu khoảng cách Manhattan (|x1-x2| + |y1-y2|) từ ô đó đến quả bom gần nhất nhỏ hơn hoặc bằng D. Hãy kiểm tra xem có đường đi nào từ (1, 1) đến (N, M) mà chỉ đi qua các ô an toàn (không nguy hiểm) không? Di chuyển được sang 4 ô kế bên.

Đầu vào:

Dòng 1: N, M, K, D.

K dòng tiếp theo: Tọa độ (r, c) của các quả bom.

Đầu ra:

In "YES" nếu có đường đi, ngược lại in "NO".

Ràng buộc:

1 <= N, M <= 1000

0 <= K <= 100

0 <= D <= 100

Ví dụ 1:

Input:

4 4 1 1 
2 3

Output:

YES

Ví dụ 2:

Input:

3 3 1 1 
2 2

Output:

NO

(Giải thích: Bom ở (2,2) với D=1 làm các ô (1,2), (2,1), (2,3), (3,2) đều nguy hiểm, chặn mọi đường đi).

Bác Mario đang đứng ở ô (1, 1) của một khu rừng hình chữ nhật kích thước N x M. Tại mỗi ô (i, j) có một số lượng nấm là A[i][j]. Bác Mario chỉ có thể di chuyển sang phải (từ ô (i, j) sang (i, j+1)) hoặc đi xuống dưới (từ ô (i, j) sang (i+1, j)). Hãy tìm đường đi từ ô (1, 1) đến ô (N, M) sao cho tổng số nấm thu được là lớn nhất.

Dữ liệu vào:

Dòng 1: Hai số nguyên N, M (1 <= N, M <= 1000).

N dòng tiếp theo, mỗi dòng chứa M số nguyên dương A[i][j] (0 <= A[i][j] <= 1000).

Dữ liệu ra:

Một số nguyên duy nhất là tổng số nấm lớn nhất thu được.

Ví dụ:

Input:

3 3 
1 2 3 
4 8 2 
1 5 3

Output:

21

Cho một bảng số kích thước N x M chỉ chứa các số 0 và 1. Hãy tìm kích thước cạnh của hình vuông lớn nhất chỉ chứa toàn số 1 trong bảng.

Dữ liệu vào:

Dòng 1: Hai số nguyên N, M (1 <= N, M <= 1000).

N dòng tiếp theo: Mỗi dòng chứa M số 0 hoặc 1.

Dữ liệu ra:

Độ dài cạnh của hình vuông lớn nhất tìm được.

Ví dụ:

Input:

4 5 
1 0 1 0 0 
1 0 1 1 1 
1 1 1 1 1 
1 0 0 1 0

Output:

2

Cho N ma trận A1, A2, ..., AN. Kích thước của ma trận Ai là D[i-1] x D[i]. Hãy tìm cách đặt ngoặc để thực hiện phép nhân các ma trận này sao cho tổng số phép nhân vô hướng cần thực hiện là ít nhất.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 100).

Dòng 2: N + 1 số nguyên D[0], D[1], ..., D[N] mô tả kích thước các ma trận.

Dữ liệu ra:

Số phép nhân ít nhất.

Ví dụ:

Input:

3 
10 100 5 50

Output:

7500

Một dãy số được gọi là Bitonic nếu nó tăng dần rồi sau đó giảm dần. Cho dãy số A gồm N phần tử, hãy tìm độ dài của dãy con Bitonic dài nhất của A.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 2000).

Dòng 2: N số nguyên A[i].

Dữ liệu ra:

Độ dài dãy con Bitonic dài nhất.

Ví dụ:

Input:

8 
1 11 2 10 4 5 2 1

Output:

6

Cho mảng A gồm N số nguyên. Bạn có thể thực hiện thao tác sau nhiều lần: Chọn một số X trong mảng, nhận X điểm, sau đó xóa tất cả các phần tử có giá trị bằng X, X-1 và X+1 khỏi mảng. Hãy tìm tổng số điểm lớn nhất có thể đạt được.

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên A[i] (1 <= A[i] <= 10^4).

Dữ liệu ra:

Tổng điểm lớn nhất.

Ví dụ:

Input:

3 
3 4 2

Output:

6

Cho dãy số A gồm N số nguyên. Với mỗi đoạn con liên tiếp A[i...j], ta tính tổng các phần tử của nó. Hãy tính tổng của tất cả các tổng đoạn con đó. (Lưu ý: Bài này có thể giải bằng toán học thuần túy hoặc quy hoạch động đơn giản).

Dữ liệu vào:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên A[i] (|A[i]| <= 10^9).

Dữ liệu ra:

Tổng của tất cả các đoạn con modulo 10^9 + 7.

Ví dụ:

Input:

3 
1 2 3

Output:

20