Kiểm tra Qui hoạch động

Hãy đếm số cách mà các số \(1, 2,\ldots,n\) có thể được chia thành hai tập hợp có tổng bằng nhau.

Ví dụ, với \(n = 7\), có \(4\) cách chia:

• \(\{1,3,4,6\}\) và \(\{2,5,7\}\)
• \(\{1,2,5,6\}\) và \(\{3,4,7\}\)
• \(\{1,2,4,7\}\) và \(\{3,5,6\}\)
• \(\{1,6,7\}\) và \(\{2,3,4,5\}\)

Input

• Gồm một dòng duy nhất chứa số nguyên \(n\) \((1 \leq n \leq 500)\).

Output

• In đáp án - số cách thoả mãn chia lấy dư cho \(10^9 + 7\).

Example

7

4

Khoảng cách chỉnh sửa giữa hai xâu là số lượng thao tác tối thiểu cần thiết để chuyển đổi một xâu thành xâu kia.

Các thao tác được phép là:

• Thêm một ký tự vào xâu
• Xóa một ký tự khỏi xâu
• Thay thế một ký tự trong xâu

Ví dụ: khoảng cách chỉnh sửa giữa LOVE và MOVIE là \(2\), vì trước tiên bạn có thể thay thế L bằng M, sau đó thêm I.

Nhiệm vụ của bạn là tính toán khoảng cách chỉnh sửa giữa hai xâu.

Input

• Dòng đầu tiên có một xâu chứa \(n\) ký tự trong khoảng từ A–Z
• Dòng thứ hai có một xâu chứa các ký tự \(m\) trong khoảng từ A–Z

Constraints

• \(1 \leq n \leq 5000\)

Output

• In một số nguyên: khoảng cách chỉnh sửa giữa các xâu

Example

LOVE
MOVIE

2

Với một hình chữ nhật \(a \times b\), nhiệm vụ của bạn là cắt nó thành các hình vuông. Trong mỗi bước, bạn có thể chọn một hình chữ nhật và cắt nó thành hai hình chữ nhật sao cho độ dài các cạnh vẫn là số nguyên. Số bước tối thiểu là bao nhiêu?

Input

• Gồm một dòng duy nhất chứa hai số nguyên \(a\) và \(b\).

Output

• In một số nguyên: số lần di chuyển tối thiểu.

Constraints

• \(1 \leq a, b \leq 500\)

Example

3 5

3

Bình và An là đôi bạn thân. Hàng ngày, hai bạn cùng nhau đi bộ tới trường. Trên con đường mà hai bạn đi có một hàng cây gồm \(n\) cây, các cây được đánh thứ tự từ \(1\) đến \(n\). Bình và An rất yêu thích hàng cây này, hai bạn đã tìm hiểu và biết được độ cao của từng cây, cây thứ \(k \ (k=1,2,…,n)\) có độ cao là \(h_k\). Thật đặc biệt, các cây có độ cao đôi một khác nhau. Một hôm, An đố Bình bài toán sau: Tìm hai số \(i,j\) là chỉ số của hai cây thỏa mãn điều kiện: \(1 \leq i < j \leq n\) và \(h_i < h_j\) để giá trị \((j-i)\) đạt giá trị lớn nhất. Bình đề nghị: “Chúng ta hãy cùng lập trình giải quyết bài toán này.”

Yêu cầu: Cho \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n\) là độ cao của \(n\) cây, hãy tìm hai số \(i,j\) là chỉ số của hai cây mà \(1 \leq i < j \leq n\) và \(h_i < h_j\) để giá trị \((j-i)\) đạt giá trị lớn nhất.

Input

• Dòng đầu chứa một số nguyên dương \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương đôi một khác nhau \(h_1,h_2,…,h_n \ (h_i \leq 10^6).\)

Output

• Một dòng chứa một số là giá trị \((j-i)\) lớn nhất tìm được. Nếu không tồn tại hai chỉ số \(i,j\) thỏa mãn thì in ra \(-1\).

Scoring

• Subtask #1 (\(50\%\) số điểm): \(n \leq 10^3\).
• Subtask #2 (\(50\%\) số điểm): \(n \leq 10^5\).

Example

4
4 2 1 3 

2

3
4 2 1 

-1

Có một lưới ô vuông có kích thước \(N × N\) được đánh chỉ số hàng từ \(1\) đến \(N\) (theo chiều từ trên xuống dưới) và chỉ số cột từ \(1\) đến \(N\) (theo chiều từ trái sang phải). Mỗi ô trong lưới được xác định vị trí bởi một cặp số \((i; j)\) trong đó \(i\) là chỉ số hàng và \(j\) là chỉ số cột.

Tại ô \((1; 1)\) người ta đặt một con robot tự hành. Mỗi lần di chuyển robot chỉ đi sang phải một ô hoặc đi xuống dưới một ô. Trong lưới ô vuông này người ta đặt một viên đá vào một số ô để làm vật cản.

Yêu cầu: Hãy tính xem có bao nhiêu đường đi từ ô \((1; 1)\) đến ô \((N; N)\). Biết rằng robot không thể đi vào ô có vật cản và hai đường đi được gọi là khác nhau nếu có ít nhất một ô thuộc đường đi này nhưng không thuộc đường đi kia.

VD: Xét lưới ô vuông kích thước \(3\times 3\) như hình vẽ sau:

Trong lưới ô vuông \(3\times 3\) này người ta đặt viên đá vào ô \((1;3)\) và ô \((2;1)\).
Với dữ kiện trên thì robot có tất cả 2 đường đi như sau:

\((1;1) → (1;2) → (2;2) → (2;3) → (3;3)\)

\((1;1) → (1;2) → (2;2) → (3;2) → (3;3)\)

Input

Đọc từ file văn bản ROBOT.INP có cấu trúc như sau:

• Dòng đầu tiên chứa 2 số nguyên dương \(N\) và \(M\) (mỗi số cách nhau 1 dấu cách; \(M < N\)).
• \(M\) dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương \(i\) và \(j\) (mỗi số cách nhau một dấu cách) là chỉ số hàng và chỉ số cột của ô được đặt vào đó một viên đá là vật cản.

Output

• Ghi ra file văn bản ROBOT.OUT một số \(k\) là số đường đi của robot từ ô \((1; 1)\) đến ô \((N; N)\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 10\).
• Subtask \(2\) (\(40\%\) số điểm): \(10 < N \le 30\).
• Subtask \(3\) (\(30\%\) số điểm): \(30 < N \le 100\).

Example

3 2
1 3
2 1

2

Cho trước một mảng độ dài \(n\) trong đó có một số vị trí chưa được xác định giá trị. Hãy đếm số cách điền giá trị vào những vị trí đó thoả mãn điều kiện sau:

• Các giá trị trong mảng là số nguyên trong khoảng từ \(1\) đến \(m\)
• Chênh lệch giữa hai phần tử liền kề không quá \(1\)

Input

• Dòng đầu tiên có hai số nguyên \(n\) và \(m\): kích thước mảng và giới hạn trên cho mỗi giá trị
• Dòng tiếp theo có \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): nội dung của mảng. Giá trị \(0\) biểu thị một giá trị không xác định

Constraints

• \(1 \leq n \leq 10^5\)
• \(1 \leq m \leq 100\)
• \(0 \leq x_i \leq m\)

Output

• In một số nguyên: số lượng dãy (cũng là số lượng cách điền) chia lấy dư cho \(10^9 + 7\)

Example

3 5
2 0 2

3

Có \(n\) dự án bạn có thể tham gia. Đối với mỗi dự án, bạn biết ngày bắt đầu và ngày kết thúc của nó và số tiền bạn sẽ nhận được làm phần thưởng. Bạn chỉ có thể tham dự một dự án trong một ngày.

Số tiền tối đa mà bạn có thể kiếm được là bao nhiêu?

Input

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng dự án.
• \(n\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(a_i\), \(b_i\) và \(p_i\): ngày bắt đầu, ngày kết thúc và phần thưởng.

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq a_i \leq b_i \leq 10^9\)
• \(1 \leq p_i \leq 10^9\)

Output

• In một số nguyên: số tiền tối đa mà bạn có thể kiếm được.

Example

4
2 4 4
3 6 6
6 8 2
5 7 3

7

Lương Xiao Lin có \(n\) em gái có mức độ yêu thương lần lượt là \(a_1, a_2, ..., a_n\). Lương muốn chọn ra \(k\) cặp em gái rời nhau. Gọi \(x\) là chênh lệch lớn nhất giữa hai bạn trong một nhóm. Vì nếu chênh lệch mức độ yêu thương giữa 2 em gái quá lớn thì có thể một em sẽ buồn. Lương là anh trai cao cả, Lương không muốn em gái nào phải buồn. Do đó, Lương muốn x càng nhỏ càng tốt. Các bạn hãy tìm \(x\) giúp Lương nhé, Lương sẽ chia có các bạn 1 em gái nếu các bạn giúp Lương.

Input

• Dòng đầu có 2 số nguyên \(n, k\).

• Dòng thứ hai có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\)

Output

• In ra một số nguyên là kết quả bài toán

Scoring

• Subtask \(1\) (\(100\%\) số điểm): \(2 \leq n \leq 3 \times 10^5, 1 \leq k \leq \dfrac{n}{2}\) và \(1 \leq a_i \leq 10^9\).

Example

6 3
1 4 3 7 11 9 

3

6 2
1 4 3 7 11 9

2

 6 1
1 4 3 7 11 9

1

Năm nay, cuộc thi chọn học sinh giỏi Duyên Hải có một nhà tài trợ trao một phần thưởng vô cùng thú vị cho thí sinh giành giải nhất môn Tin học. Số tiền thưởng mà thí sinh nhận được chính là số điểm mà thí sinh đó lấy được trong trò chơi mà nhà tài trợ đưa ra:

Cho một dãy \(n\) số nguyên (\(a_1, a_2, …, a_n\)). Người chơi có thể thực hiện những thao tác sau đây trên dãy đã cho:

• Chọn một số \(a_i\) bất kỳ thì nhận được số điểm là \(a_i\) (\(i = 1÷n\)).
• Đồng thời cũng phải xóa đi tất cả các số có giá trị là (\(a_i – 1\)) và (\(a_i + 1\)) có trong dãy ngay sau đó.

Yêu cầu: Ban đầu người chơi có 0 điểm. Bạn hãy cho biết số tiền lớn nhất mà thí sinh giải nhất có thể nhận được từ nhà tài trợ.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1\le n \le 20000\))
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, …, a_n\) (\(1\le a_i \le10000\)), mỗi số cách nhau một dấu cách.

Output

• Đưa ra một số nguyên là số tiền lớn nhất mà thí sinh giải nhất có thể nhận được.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1 \le n \le 1000\), \(1\le a_i \le 100\).
• Subtask \(2\) (\(40\%\) số điểm): \(1\le n \le 20000\), \(1\le a_i \le 10000\).

Example

3
3 4 2

6

6
2 2 3 3 3 4

9