Một robot đứng ở ô (1, 1) của bảng kích thước M x N. Robot chỉ được đi xuống dưới hoặc đi sang phải. Hãy đếm số cách để robot đi đến ô (M, N). Dữ liệu vào:

Hai số M và N.

Dữ liệu ra:

Số cách đi (chia dư cho 10^9 + 7).

Ràng buộc:

1 <= M, N <= 1000

Ví dụ:

Input:

3 3

Output:

6

Một con bò đi từ ô (1, 1) đến ô (M, N). Tại mỗi ô (i, j) có A[i][j] bụi cỏ. Con bò chỉ được đi xuống hoặc sang phải. Hãy tìm đường đi sao cho tổng số bụi cỏ ăn được là nhiều nhất.

Dữ liệu vào:

Dòng 1: M và N.

M dòng tiếp theo: Mỗi dòng N số nguyên biểu thị số lượng cỏ.

Dữ liệu ra:

Tổng số cỏ lớn nhất ăn được.

Ràng buộc:

1 <= M, N <= 100

0 <= A[i][j] <= 100

Ví dụ:

Input:

2 3 
1 2 4 
3 5 1

Output:

10

Bạn có các loại tiền mệnh giá C[1], C[2], ..., C[N]. Hãy đếm xem có bao nhiêu cách để tạo ra số tiền S từ các loại tiền đó. Giả sử số lượng mỗi loại tiền là vô hạn.

Dữ liệu vào:

Dòng 1: N và S.

Dòng 2: Các mệnh giá tiền.

Dữ liệu ra:

Số cách đổi (chia dư cho 10^9 + 7).

Ràng buộc:

1 <= N <= 100

1 <= S <= 1000

Ví dụ:

Input:

3 5 
1 2 5

Output:

4

Giải thích: (1+1+1+1+1), (1+1+1+2), (1+2+2), (5).

Vẫn là bài toán đổi tiền, nhưng lần này hãy tìm số lượng đồng xu ít nhất để tạo ra số tiền S. Nếu không thể tạo ra, in -1.

Dữ liệu vào:

Dòng 1: N và S.

Dòng 2: Các mệnh giá tiền.

Dữ liệu ra:

Số đồng xu ít nhất.

Ràng buộc:

1 <= N <= 100

1 <= S <= 10000

Ví dụ:

Input:

3 11 
1 3 5

Output:

3

Giải thích: 5 + 3 + 3 = 11.

Một thanh gỗ dài N mét. Có bảng giá bán các đoạn gỗ độ dài 1, 2, ..., N. Hãy cắt thanh gỗ thành các đoạn nhỏ sao cho tổng giá bán thu được là cao nhất.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: N số nguyên là giá bán của đoạn gỗ độ dài 1, 2, ..., N.

Dữ liệu ra:

Giá trị lớn nhất thu được.

Ràng buộc:

1 <= N <= 100

Ví dụ:

Input:

4 
1 5 8 9

Output:

10

Giải thích: Cắt thành 2 đoạn độ dài 2 (giá 5+5=10).

Một dãy phố có N ngôi nhà, mỗi nhà có chứa một số tiền A[i]. Tên trộm muốn lấy được nhiều tiền nhất nhưng không được trộm 2 ngôi nhà nằm liền kề nhau (vì sẽ kích hoạt báo động). Hãy tính số tiền lớn nhất hắn có thể trộm.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: Số tiền trong các ngôi nhà.

Dữ liệu ra:

Số tiền lớn nhất.

Ràng buộc:

1 <= N <= 1000

Ví dụ:

Input:

4 
1 2 3 1

Output:

4

Giải thích: Trộm nhà 1 (1) và nhà 3 (3). Tổng = 4.

Cho dãy số A gồm N số nguyên dương. Hãy kiểm tra xem có tồn tại một dãy con (tập hợp con) nào của A có tổng bằng S hay không.

Dữ liệu vào:

Dòng 1: N và S.

Dòng 2: Dãy A.

Dữ liệu ra:

In "YES" nếu tồn tại, ngược lại in "NO".

Ràng buộc:

1 <= N <= 100

1 <= S <= 10000

Ví dụ:

Input:

5 10 
1 2 3 4 5

Output:

YES

Cho N món quà, món thứ i có giá trị A[i]. Hãy chia N món quà này thành 2 phần sao cho chênh lệch tổng giá trị giữa 2 phần là nhỏ nhất.

Dữ liệu vào:

Dòng 1: N.

Dòng 2: Giá trị các món quà.

Dữ liệu ra:

Chênh lệch nhỏ nhất.

Ràng buộc:

1 <= N <= 100

Tổng giá trị <= 10000

Ví dụ:

Input:

4 
1 6 11 5

Output:

1

Giải thích: Nhóm (1, 5, 6) tổng 12 và Nhóm (11) tổng 11. Chênh lệch 1.