DP marathon

Có \(N\) hòn đá được đánh số từ \(1,2,\ldots,N\). Hòn đá thứ \(i\) có chiều cao là \(h_i\).

Ban đầu, có một con ếch đang ngồi ở hòn đá thứ nhất. Con ếch sẽ lặp đi lặp lại thao tác sau nhiều lần để đến được hòn đá thứ \(N\):

• Nếu con ếch đang ở hòn đá thứ \(i\), nó có thể nhảy đến hòn đá thứ \(i+1\) hoặc hòn đá thứ \(i+2\) với chi phí là \(|h_i-h_j|\) (\(j\) là hòn đá mà con ếch nhảy đến).

Bạn hãy giúp con ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất tới hòn đá thứ \(N\) nhé.

Input

• Dòng thứ nhất chứa một số nguyên dương \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(h_1,h_2,\ldots,h_N\) (\(1 \leq h_i \leq 10^4\)).

Output

• Một dòng chứa một số nguyên duy nhất là kết quả bài toán.

Example

4
10 30 40 20

30

2
10 10

0

Có \(N\) hòn đá, được đánh số từ \(1, 2, ..., N\). Độ cao của hòn đá thứ \(i\) là \(h_i\).

Có một con ếch ban đầu ở hòn đá thứ \(1\). Nó sẽ lặp lại các thao tác sau nhiều lần để tới được hòn đá thứ \(N\).

• Nếu con ếch đang ở hòn đá thứ \(i\), nó có thể nhảy đến hòn đá thứ \(i + 1, i + 2, ..., i + K\). Với chi phí cho mỗi lần nhảy là \(|h_i - h_j|\) (\(j\) là hòn đá mà con ếch nhảy đến)

Bạn hãy giúp con ếch tìm chi phí tối thiểu để nhảy từ hòn đá thứ nhất tới hòn đá thứ \(N\) nhé.

Input

• Dòng 1: Ghi hai số nguyên \(N\) và \(K\) (\(2 \leq N \leq 10^5\), \(1 \leq K \leq 100\)).
• Dòng 2: ghi \(N\) số nguyên dương \(h_1, h_2, ..., h_N\) (\(1 \leq h_i \leq 10^4\)).

Output

• Ghi một số nguyên duy nhất là chi phí tối thiểu để nhảy từ hòn đá thứ nhất đến hòn đá thứ \(N\).

Example

5 3
10 30 40 50 20

30

3 1
10 20 10

20

Có \(N\) hòn đá được đánh số từ \(1\) đến \(N\). Ứng với mỗi \(i\) \((1\le i\le N)\), độ cao của hòn đá thứ \(i\) là \(h_i\), và ở đây các \(h_i\) thỏa mãn điều kiện \(h_1<h_2<...<h_N\).

Có một chú ếch, ban đầu ở hòn đá \(1\). Chú ếch này sẽ lặp lại hành động sau với một số lần tùy ý cho đến khi đến được hòn đá \(N\).

• Nếu hiện tại, chú ếch đang ở vị trí thứ \(i\), thì trong \(1\) lần chú có thể nhảy đến một trong các vị trí từ \(i+1\) đến \(N\) (tức là: \(i+1\) hoặc \(i+2\) hoặc ... hoặc \(N\)) với chi phí tương ứng là \((h_j-h_i)^2+C\), ở đây \(j\) \((i+1\le j\le N)\) là vị trí hòn đá mà chú muốn nhảy đến và \(C\) là một hằng số cho trước.

Tìm chi phí tối thiểu để chú ếch này có thể nhảy đến hòn đá thứ \(N\).

Input

• Dòng thứ nhất chứa hai số nguyên \(N, C\) \((2\le N\le 2 \cdot 10^5, 1\le C\le 10^{12})\).
• Dòng thứ hai chứa \(N\) số nguyên \(1\le h_1<h_2<...<h_N\le 10^6\).

Output

• Chi phí tối thiểu cần tìm.

Example

5 6
1 2 3 4 5

20

Nguồn: Tham khảo từ Atcoder

Kì nghỉ hè của Taro sẽ bắt đầu vào ngày mai và cậu bé đã quyết định lên kế hoạch cho kì nghỉ ngay từ bây giờ.

Kì nghỉ gồm \(N\) ngày. Ngày thứ \(i\), Taro sẽ chọn một trong các hoạt động sau:

• A: Bơi ở biển. Đạt được \(a_i\) điểm hạnh phúc.
• B: Bắt côn trùng trên núi. Đạt được \(b_i\) điểm hạnh phúc.
• C: Làm bài tập về nhà. Đạt được \(c_i\) điểm hạnh phúc.

Vì Taro dễ chán nên cậu bé không thể làm cùng một hoạt động trong 2 ngày liên tiếp trở lên.

Hãy tính điểm hạnh phúc lớn nhất mà Taro có thể đạt được.

Input

• Dòng đầu: Ghi số nguyên \(N\) (\(1 \leq N \leq 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng ghi \(3\) số nguyên \(a_i, b_i, c_i\) (\(1 \leq a_i, b_i, c_i \leq 10^4\)).

Output

• Ghi một số nguyên duy nhất là tổng điểm hạnh phúc lớn nhất mà Taro có thể đạt được.

Example

3
10 40 70
20 50 80
30 60 90

210

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

46

Cho ma trận gồm \(H\) hàng và \(W\) cột. Gọi \((i,j)\) là ô vuông ở hàng thứ \(i\) và cột thứ \(j\).

Với mỗi \(i,j(1\le i\le H,1\le j\le W)\), ô vuông \((i,j)\) được mô tả bởi kí tự \(a_{i,j}\). Nếu \(a_{i,j}=\). thì ô vuông này trống rỗng, nếu \(a_{i,j}=\) # thì ô vuông này chứa vật cản.

\(Kaninho\) bắt đầu ở ô vuông \((1,1)\) và muốn đến ô vuông \((H,W)\) bằng việc lặp lại các bước: Đi sang phải hoặc đi xuống dưới ô trống kề với nó.

Tìm số con đường mà \(Kaninho\) có thể đi được từ ô \((1,1)\) đến ô \((H,W)\). Bởi vì đáp án có thể lớn, nên trước khi in ra cần lấy mod \(10^9+7\).

Input

• Dòng thứ nhất chứa hai số nguyên \(H,W(2\le H,W\le 1000)\)

• \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) kí tự \(a_{i,1},a_{i,2},...,a_{i,W}(1\le i\le H)\) - thể hiện ma trận \(Kaninho\) cần đi. Biết rằng đề ra luôn đảm bảo các ô \((1,1)\) và \((H,W)\) đều trống.

Output

• In ra đáp án cần tìm.

Example

3 4
...#
.#..
....

3

Cho \(N\) là một số nguyên dương lẻ.

Có \(N\) đồng xu, được đánh số \(1,2,3,\cdots,N\). Với mỗi \(i(1 \leq i \leq N)\), khi đồng xu \(i\) được gieo, xác suất nó xảy ra mặt ngửa là \(p_i\) và xác suất nó xảy ra mặt úp là \(1−p_i\).

Kaninho gieo \(N\) đồng xu cùng một lúc. Tính xác suất để ta thu được số lượng đồng xu ngửa lớn hơn số lượng đồng xu úp.

Input

• Dòng thứ nhất chứa số nguyên dương lẻ \(N(1 \leq N \leq 2999)\)
• Dòng thứ hai chứa \(n\) số thực có 2 chữ số ở hàng thập phân \(p_i(0<p_i<1)\)

Output

• In ra đáp án cần tìm. (Gọi \(x\) là đáp án của bạn, \(y\) là đáp án của bài toán, thì \(x\) được chấp nhận là đúng nếu \(|x−y|<10^{−9}\))

Example

3
0.30 0.60 0.80 

0.612

Có \(N\) cái đĩa , được đánh số \(1,2,3,\cdots,N\). Ban đầu, với mỗi \(i(1 \leq i \leq N)\), cái đĩa thứ \(i\) có \(a_i(1 \leq a_i \leq 3)\) miếng sushi.

Kaninho sẽ lặp lại phép toán dưới đây cho đến khi tất cả các miếng sushi trên các đĩa được ăn hết:

Thả con xúc sắc có \(N\) mặt được đánh số \(1,2,3,\cdots,N\) (xác suất xuất hiện \(N\) mặt này là như nhau), và gọi \(i\) là mặt của con xúc sắc sau khi thả. Nếu có một vài miếng sushi trên đĩa thứ \(i\), Kaninho sẽ ăn 1 cái trong số chúng, còn nếu không có cái nào hết, thì Kaninho sẽ không làm gì cả.
Tìm giá trị kì vọng của số lần thực hiện phép toán trên trước khi tất cả các miếng sushi trên các đĩa được ăn hết.

Input

• Dòng thứ nhất chứa số nguyên \(N(1 \leq N \leq 300)\)
• Dòng thứ hai chứa \(N\) số \(a_i(1 \leq a_i \leq 3\))

Output

• In ra giá trị kì vọng cần tìm. (gọi \(x\) là đáp án của bạn và \(y\) là đáp án của bài toán thì đáp án \(x\) được chấp nhận nếu \(|x−y|<10^{−9}\)

Example

3
1 1 1 

5.5

Một dãy số được gọi là dãy số đặc biệt khi ta đọc dãy từ trái sang phải cũng giống như khi đọc từ phải sang trái.

Chẳng hạn:

• Dãy gồm các số \((21, 1, 9, 1, 21)\) là dãy số đặc biệt.
• Dãy gồm các số \((1, 7, 8, 9, 1)\) không phải là dãy số đặc biệt.

Yêu cầu: Cho số nguyên dương \(N\) và dãy số \(A\) gồm \(N\) phần tử \(a_1, a_2, \ldots, a_n\), mỗi phần tử là một số nguyên dương. Hãy tìm số lượng ít nhất phần tử cần chèn thêm vào dãy \(A\) để dãy \(A\) thành dãy số đặc biệt.

Input

• Dòng đầu là số tự nhiên \(N \leq 1000\);
• Dòng thứ 2 gồm \(N\) số nguyên dương \(a_1, a_2, a_3, \ldots, a_n\) \((0 \leq a_i \leq 10^9)\).

Output

• Ghi kết quả tìm được ra màn hình.
• Các số trên một dòng của tập input/output phải cách nhau ít nhất một dấu cách.

Example

5
1 7 8 9 1

2