DP Marathon

Có \(N\) hòn đá được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), chiều cao của hòn đá thứ \(i\) là \(h_i\)

Có một con ếch ban đầu ở hòn đá \(1\). Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá \(N\).

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

Tìm chi phí tối thiểu để nó đến được hòn đá thứ \(N\).

Input

• Dòng thứ nhất chứa số nguyên \(N(2\le N\le 10^5)\)

• Dòng thứ hai chứa \(N\) số nguyên : \(h_1,h_2,...,h_N\) với \(1\le h_i\le 10^4\)

Output

• In ra chi phí tối thiểu cần tìm

Example

4
10 30 40 20

30

Có \(N\) hòn đá được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), chiều cao của hòn đá thứ \(i\) là \(h_i\)

Có một con ếch ban đầu ở hòn đá \(1\). Nó lặp lại hành động sau với một số lần bất kì cho đến khi nó đến được hòn đá \(N\).

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

Tìm chi phí tối thiểu để nó đến được hòn đá thứ \(N\).

Input

• Dòng thứ nhất chứa hai số nguyên \(N,K(2\le N\le 10^5,1\le K\le 100)\)

• Dòng thứ hai chứa \(N\) số nguyên : \(h_1,h_2,...,h_N\) với \(1\le h_i\le 10^4\)

Output

• In ra chi phí tối thiểu cần tìm

Example

5 3
10 30 40 50 20

30

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^5)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^9)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90

Kì nghỉ hè của \(Kaninho\) bắt đầu vào ngày mai, và anh ấy quyết định lên kế hoạch ngay từ bây giờ

Kì nghỉ gồm \(N\) ngày. Với mỗi \(i(1\le i\le N)\), \(Kaninho\) sẽ chọn \(1\) trong \(3\) hoạt động dưới đây và thực hiện nó vào ngày thứ \(i\) :

• A: Đi bơi ở biển. Thu về \(a_i\) độ "hạnh phúc".

• B: Đi bắt sâu bọ ở trên núi. Thu về \(b_{i}\) độ "hạnh phúc".

• C: Làm bài tập về nhà. Thu về \(c_i\) độ "hạnh phúc".

Bởi vì \(Kaninho\) dễ dàng buồn chán, nên anh ấy không thể thực hiện hai hoạt động giống nhau trong \(2\) ngày (hoặc hơn) liên tiếp.

Tìm độ "hạnh phúc" lớn nhất mà \(Kaninho\) có thể đạt được.

Input

• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 10^5)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa \(3\) số nguyên \(a_i,b_i,c_i(1\le a_i,b_i,c_i\le 10^4)\)

Output

• In ra độ "hạnh phúc" lớn nhất cần tìm

Example

3
10 40 70
20 50 80
30 60 90

210

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^9)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^3)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90

SPyofgame là một điệp viên của tổ chức O.W.C.A với bí danh H (H là gì thì chắc ai cũng nhận ra). Mỗi tháng, anh ta nhận được một danh sách nhiệm vụ của mình. Dù là thành viên lâu năm nhưng SPyofgame khá lười biếng, suốt ngày chỉ lo chơi surviv và nhắn tin cho bạn gái, anh ta không thể tính toán được xác suất để hoàn thành được \(N\) nhiệm vụ cụ thể được giao nên thường bị phạt tiền. Lần này, bạn hãy giúp anh ấy tính xác suất để anh ấy có thể hoàn thành được nhiệm vụ.

Input

Dòng đầu tiên là số nguyên dương \(N\), số lượng nhiệm vụ được giao \((1 \leq N \leq 20)\)
\(N\) dòng tiếp theo, mỗi dòng bao gồm \(N\) số nguyên dương \(x\) là xác xuất(%) để hoàn thành được nhiệm vụ con thứ \(i\) \((1 \leq i \leq N, 0 \leq x \leq 100)\)

Output

1 dòng duy nhất là xác suất để SPyofgame có thể hoàn thành \(N\) nhiệm vụ, đáp án được chấp nhận nếu sai số không quá \(10^{-6}\)

Example

3
10 6 4
4 2 10
25 12 7 

0.150000000000

Cho hai xâu \(s\) và \(t\) chỉ gồm các chữ cái thường \('a'..'z'\). Tìm xâu con chung dài nhất (subsequence) của hai xâu \(s\) và \(t\)

Input

• Dòng thứ nhất chứa xâu \(s(1\le |s|\le 3000)\)

• Dòng thứ hai chứa xâu \(t(1\le |t|\le 3000)\)

Output

• In ra xâu chung dài nhất cần tìm. Nếu có nhiều đáp án in ra bất kì !

Chú ý: Một xâu con của một xâu \(x\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(x\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Example

axyb
abyxb

axb

Cho đồ thị có hướng gồm \(N\) đỉnh và \(M\) cạnh. Các đỉnh được đánh số \(1,2,...,N\) và với mỗi \(i(1\le i\le M)\), cạnh có hướng thứ \(i\) sẽ đi từ đỉnh \(x_i\) đến đỉnh \(y_i\). \(G\) không chứa bất kì chu trình có hướng nào !

Tìm độ dài lớn nhất của đường đi có hướng trong \(G\). Ở đây, độ dài của đường đi có hướng chính là số cạnh trong nó.

Input

• Dòng thứ nhất chứa \(2\) số nguyên \(N,M(2\le N\le 10^5; 1\le M\le 10^5)\)

• \(M\) dòng tiếp theo mỗi dòng chứa hai số nguyên \(x_i,y_i(1\le x_i,y_i\le N )\) (Ở đây các cặp \((x_i,y_i)\) phân biệt nhau và đề đảm bảo rằng, \(G\) không chứa bất kì chu trình có hướng nào).

Example

3 2
1 2
2 3

2

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

Sau một chuỗi thua cược vì tụt rank liên tục, SPyofgame đang mắc một khoản nợ. Nhưng vì mải dùng tiền mua quà cho bạn gái nên giờ SPyofgame đã hết tiền để trả nợ. Vì thế, SPyofgame phải chơi một trò chơi do chủ nợ đưa ra. Nếu chiến thắng, số tiền nợ sẽ được giảm một nửa, còn nếu không, SPyofgame sẽ phải nhường bạn gái cho chủ nợ. Trò chơi được mô tả như sau:

Người chủ nợ sẽ đặt \(N\) số nguyên dương vào một vòng tròn và thực hiện các yêu cầu sau:

Người chơi đầu sẽ chọn một số nguyên dương bất kỳ
Người chơi thứ hai lấy một trong hai số liền kề với số mà người chơi thứ nhất đã lấy.
Người chơi tiếp theo sẽ lấy một số liền kề với bất kỳ số đã lấy trước đây. Trò chơi tiếp diễn cho đến khi hai người lấy hết được toàn bộ số trong vòng tròn. Người thắng cuộc là người lấy được nhiều số lẻ hơn (số chia \(2\) dư \(1\)).
Biết rằng SPyofgame sẽ luôn chơi tối ưu, nhưng anh ta không biết thực lực cụ thể của chủ nợ. Vì là người có quyền, chủ nợ sẽ luôn là người chơi trước. Chủ nợ muốn nhờ bạn tính xem có bao nhiêu cách chọn số đầu tiên để người chiến thắng là chủ nợ (đến đây chắc ai cũng biết chủ nợ là ai rồi)

Input

• Dòng đầu tiên chứa số nguyên dương \(N(1 \leq N \leq 100)\), là số lượng số được đặt trên vòng tròn. Dòng thứ hai gồm \(N\) số nguyên dương, số thứ \(i\) có giá trị \(a[i]\) là giá trị của vị trí thứ \(i\) trên hình tròn. \((1 \leq a[i] \leq 1000)\)

Output

• Một dòng duy nhất là kết quả của bài toán.

Example

3
3 1 5 

3

Khi được học về LCS Tèo rất hứng thú vì học được phương pháp hay, học được cách vận dụng biến đổi các bài toán liên quan về dạng quen thuộc để ứng dụng được LCS vào để giải. Biết Tèo đang hứng thú, Tí đố Tèo một bài toán như sau:

Cho hai xâu kí tự số \(X\) và \(Y\), tìm một xâu con chung có giá trị lớn nhất của hai xâu đã cho. Ví dụ \(X\) = \('1003456'\) và \(Y\) = \('001435'\): Một số xâu con chung như \('00'\), \('0035'\), \('135'\), \('145'\), \(\cdots\) Xâu con chung có giá trị lớn nhất là \('145'\). Xâu con chung phải lớn nhất phải là một số không chứa số \(0\) vô nghĩa.

Bạn hãy giúp Tèo viết chương trình tìm xâu con chung có giá trị lớn nhất đó để Tèo có thể kiểm tra đáp án của mình.

Input

• Dòng 1 là xâu kí tự \(X\)
• Dòng 2 là xâu kí tự \(Y\)

Hai xâu chỉ chứa kí tự số. Độ dài mỗi xâu số không quá \(1000\).

Output

• in ra dòng 1 là độ dài của xâu con chung lớn nhất cần tìm.
• Dòng thứ hai in ra xâu con chung lớn nhất theo đúng định dạng đã cho ở ví dụ bên dưới.

Example

1003456
001435   

3
LCS MAX NUMBER is 145

10103456
0101435 

5
LCS MAX NUMBER is 10145

000314
3000410 

2
LCS MAX NUMBER is 34

12345
6789 

0
LCS MAX NUMBER is NULL

60005
90204    

1
LCS MAX NUMBER is 0

\(Kaninho\) và \(Henry\) chơi với nhau một trò chơi như sau:

Ban đầu, họ được cho một dãy số \(a=(a_1,a_2,\cdots,a_n)\). Họ lần lượt thực hiện phép toán dưới đây cho đến khi dãy \(a\) rỗng, bắt đầu từ \(Kaninho\):

Loại bỏ phần tử đầu tiên hoặc cuối cùng của dãy \(a\). Người chơi đó sẽ kiếm được \(x\) điểm, với \(x\) là phần tử bị loại bỏ.
Gọi \(X\) và \(Y\) lần lượt là số điểm của \(Kaninho\) và \(Henry\) sau khi trò chơi kết thúc. \(Kaninho\) cố gắng làm \(X−Y\) lớn nhất có thể, trong khi \(Henry\) muốn \(X−Y\) nhỏ nhất có thể.

Giả sử cả hai người đều chơi tối ưu, tìm giá trị của \(X−Y\).

Input

• Dòng thứ nhất chứa số nguyên \(N(1 \leq N \leq 3000)\)
• Dòng thứ hai, chứa \(n\) số nguyên \(a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)\)

Output

• In ra giá trị cần tìm

Example

4
10 80 90 30 

10

Cho tập hợp gồm \(N\) số nguyên dương \(A=\) {\(a_1,a_2,...,a_n\)}. Kaninho và Henry chơi với nhau một trò chơi như sau:

Ban đầu, chúng ta có một cái cột rỗng chứa K viên đá. Hai người chơi sẽ lần lượt thực hiện phép toán sau, bắt đầu từ Kaninho:

Chọn một phần tử \(x\) của tập \(A\), và loại bỏ đi chính xác \(x\) hòn đá từ cột đó.
Người nào không thể thực hiện được phép toán trên, thì đó là người thua cuộc. Giả sử cả hai người đều chơi tối ưu, xác định người chiến thắng.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N,K(1 \leq N \leq 100,1 \leq K \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên dương thỏa mãn \(1 \leq a_1 < a_2 < a3 < \cdots <a_n \leq K\).

Output

• Nếu Kaninho là người thắng cuộc, in ra \("\)\(First"\), ngược lại nếu Henry thắng in ra \("\)\(Second"\).

Example

2 4 
2 3 

First

Cho hai xâu \(S\) và \(T\) chỉ gồm các chữ cái thường 'a'..'z'. Tìm độ xâu con chung dài nhất (subsequence) của hai xâu \(S\) và \(T\).

Input

• Gồm hai dòng
• Dòng thứ nhất chứa xâu \(S\).
• Dòng thứ hai chứa xâu \(T\).

Output

• In ra độ dài xâu con chung dài nhất cần tìm.
  Chú ý: Một xâu con của một xâu \(X\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(X\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(|S|, |T| \le 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(|S|, |T| \le 10^4\).

Example

axyb
abyxb 

3

Nguồn: Cấp độ khó hơn của bài Xâu con chung dài nhất của jumptozero

Cho ba số nguyên dương \(A,B,K\). Có bao nhiêu số tự nhiên trong khoảng \([A;B]\) có tổng các chữ số bằng \(K\)?

Input

• Một dòng duy nhất là ba số nguyên dương \(A,B,K\) \((1 \leq A,B \leq 10^{18},1 \leq S \leq 200)\)

Output

• Dòng thứ nhất là số lượng số trong khoảng \([A;B]\) có tổng các chữ số bằng \(S\).
• Dòng thứ hai là số nhỏ nhất trong khoảng \([A;B]\) thỏa mãn. Nếu không tồn tại thì xuất \(−1\)

Example

1 9 5 

1
5

Có \(N\) đứa trẻ, được đánh số \(1,2,\cdots,N\)
\(Kaninho\) quyết định đem \(K\) viên kẹo chia cho \(N\) đứa trẻ này. Ở đây, với mỗi \(i(1 \leq i \leq N)\), đứa trẻ thứ \(i\) được nhận \(x\) viên kẹo với \(x \in [0;a_i]\). Biết rằng, \(Kaninho\) chia hết tất cả \(K\) viên kẹo cho \(N\) đứa trẻ này, không để lại viên nào.

Tìm số cách mà \(Kaninho\) có thể chia hết tất cả \(K\) viên kẹo cho \(N\) đứa trẻ này. Vì đáp án có thể lớn nên trước khi in ra ta cần lấy \(mod\) \(10^9+7\). Ở đây, hai cách chia được coi là khác nhau khi tồn tại một đứa trẻ nhận một số lượng kẹo khác nhau.

Input

• Dòng thứ nhất chứa hai số nguyên \(N\),\(K(1 \leq N \leq 100,0 \leq K \leq 10^5)\)
• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\cdots,a_N(0 \leq a_i \leq K)\)

Output

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

Example

3 4
1 2 3 

5

Trong một cây nhị phân có độ dài vô hạn:

• Gốc ban đầu có giá trị là 1
• Mỗi node sẽ có hai gốc con, 1 gốc bên trái và 1 gốc bên phải. Nếu node được gán nhãn X, thì hai gốc con sẽ có nhãn là 2X (bên trái) và 2X+1 (bên phải).
• Đi từ đỉnh xuống, ta có thể đi qua gốc con bên trái, hoặc gốc con bên phải, hoặc dừng lại ở vị trí đang đứng.

Cho bài toán sau: Đi từ gốc xuống:

• Nếu là L thì sẽ đi qua gốc con bên trái.
• Nếu là R thì sẽ đi qua gốc con bên phải.
• Nếu là P thì sẽ dừng lại.
• * là ẩn với 3 cách đi: trái, phải hoặc dừng lại.

Ví dụ: L* thì ta có thể đi: LR, LP hoặc LL.
Bạn hãy tính tổng các giá trị nhãn của các nút là đích đến mà có thể đi tới được.

Input

• Một dòng duy nhất là một chuỗi biểu diễn đường đi. Độ dài chuỗi không vượt quá 10000

Output

• Kết quả bài toán.

Example

** 

33

Cho hai xâu S và T chỉ gồm các chữ cái thường 'a'..'z'. Tìm độ dài xâu con chung dài nhất (subsequence) của hai xâu S và T.

Input

• Dòng đầu tiên chứa duy nhất một số \(T \leq 30\) là số lượng bộ test.
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(5000\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là độ dài xâu con chung dài nhất tìm được.

Example

1
wigwwnydtyo
kwmmka

1

Đấu trường \(100\) là \(1\) gameshow nổi tiếng với thể thức \(1\) người chơi chính đấu với 100 người chơi khác. Thí sinh trả lời các câu hỏi và phải loại \(100\) người thi đấu với anh ta. Mọi người trả lời cùng một câu hỏi trong mỗi vòng và những người trả lời sai câu hỏi sẽ bị out. Trong mỗi vòng, tất cả các đối thủ đều có giá trị như nhau và tất cả các đối thủ cộng lại có giá trị \(100000\) USD. Số tiền kiếm được trong một vòng bằng tổng giá trị của những người bị out trong vòng đó. Ví dụ: nếu có 10 đối thủ tại một thời điểm nào đó, mỗi người trong số họ trị giá \(10000\) USD và thí sinh sẽ nhận được 30000 USD nếu có 3 người bị out trong vòng đó.

Giả sử vào thời điểm bất kỳ, có tất cả N đối thủ. Hãy tính số tiền lớn nhất mà người chơi có thể giành được sau chính xác K vòng.

Input

• Một dòng duy nhất là hai số nguyên dương \(N, K (1 ≤ K ≤ N ≤ 100000)\)

Output

• Số tiền mà người chơi có thể có lớn nhất chia cho \(100000\). Sai số không được vượt quá \(10^{-6}\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): K, N \(\leq\) 100
• Subtask \(2\) (\(50\%\) số điểm): K, N \(\leq\) 10000

Example

5 3 

2.100000000

galindo.md
Sau một thời gian gieo rắc nỗi sợ ra toàn thế giới nhưng lại bị lôi ra làm trò đùa ở Việt Nam. Jonathan Galindo quyết định đến đây để xem con người ở đây như thế nào. Ở đây anh bị choáng ngợp, thu hút bởi những điệu múa quạt của anh Bảnh, những tiết dạy làm người của thầy Huấn, những điệu nhảy sexy của Trần Đức Bo hay là bác Trần Tiger cầm súng bắn chết mấy thằng chửi thề. Vì quá yêu mến đất nước Việt Nam nên Jonathan Galindo quyết định giúp đất nước Việt Nam sánh vai với các cường quốc năm châu. Nhưng để làm được điều đó thì Galindo phải giải được 1 bài toán mà thánh coder cũng đồng thời là người đẹp trai top 7 tỉ thế giới bin9638 đưa ra. Bạn hãy giúp Galindo giải bài toán nhé !

Bạn được đưa ra một mảng số nguyên \(a_1,..., a_n (1 \leq a_i \leq n)\). Mức độ “To và tròn” của một đoạn con liên tiếp là số cặp các phần tử bằng nhau của đoạn đó. Hãy chia dãy thành \(k\) đoạn con không trống để tổng mức độ “To và tròn” của các đoạn con là nhỏ nhất có thể (Vì bin9638 thích “Lép và phẳng”).

Input

• Dòng đầu chứa 2 số nguyên \(n, k (2 \leq n \leq 10^5, 2 \leq k \leq min (n, 20))\)
• Dòng tiếp theo chứa dãy \(a_1, a_2, ..., a_n (1 \leq a_i \leq n)\).

Output

• Một dòng duy nhất là mức độ “To và tròn” tối thiểu.

Scoring

• Subtask \(1\) (\(1\%\) số điểm): \(n=10\)
• Subtask \(2\) (\(49\%\) số điểm): \(n \leq 1000\)
• Subtask \(3\) (\(48\%\) số điểm): \(n<10^5\)
• Subtask \(4\) (\(1\%\) số điểm): \(n=10^5\)
• Subtask \(5\) (\(1\%\) số điểm): không ràng buộc gì thêm

Example

7 3
1 1 3 3 3 2 1 

1

13 3
1 2 2 2 1 2 1 1 1 2 2 1 1 

9

Có \(N\) hủ kẹo dẻo được đặt trên một hàng. Ban đầu, hủ thứ \(i\) có độ ngọt là \(a_i\).

\(Kaninho\) cố gắng kết hợp tất cả các hủ kẹo này thành một hủ kẹo lớn hơn. Anh ấy thực hiện phép toán dưới đây nhiều lần cho đến khi chỉ còn một hủ kẹo duy nhất thì dừng:

• Chọn \(2\) hủ kẹo kề nhau bất kì và kết hợp chúng lại thành một hủ kẹo. Hủ kẹo mới này có độ ngọt là \(x+y\), trong đó \(x,y\) lần lượt là độ ngọt của hai hủ kẹo trước đó. Và việc này tốn chi phí là \(x+y\). Mối quan hệ về vị trí giữa các hủ kẹo vẫn không thay đổi khi ta kết hợp chúng lại với nhau.

Input

• Dòng thứ nhất chứa số nguyên \(N(2\le N\le 400)\)

• Dòng thứ hai chứa \(N\) số nguyên \(a_i(1\le a_i\le 10^9)\).

Output

• In ra chi phí tối thiểu để kết hợp tất cả các hủ kẹo trên thành \(1\) hủ duy nhất.

Example

4
10 20 30 40 

190

Có \(N\) người đàn ông và \(N\) người phụ nữ, được đánh số \(1,2,3,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), độ "hợp nhau" của người đàn ông thứ \(i\) và người phụ nữ thứ \(j\) được kí hiệu bởi \(a_{i,j}\). Người đàn ông thứ \(i\) "hợp" với người phụ nữ thứ \(j\) nếu \(a_{i,j}=1\), ngược lại \(a_{i,j}=0\).

\(Kaninho\) muốn tạo ra \(N\) cặp "hợp nhau". Trong đó, mỗi người đàn ông và mỗi người phụ nữ phải thuộc về chính xác một cặp.

Tìm số cách mà \(Kaninho\) có thể tạo ra \(N\) cặp hợp nhau, vì đáp án có thể lớn, nên cần phải lấy mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 21)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,N}(1\le i\le N,a_{i,j}\in \left\{0,1\right\})\)

Output

• In ra giá trị cần tìm

Example

3
0 1 1
1 0 1
1 1 1 

3

Có một cây \(N\) đỉnh, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\leq i\leq N-1)\), cạnh thứ \(i\) nối đỉnh \(x_i\) và \(y_i\)

\(Kaninho\) quyết định tô mỗi đỉnh màu đen hoặc trắng. Ở đây, hai đỉnh kề nhau không được tô cùng màu đen.

Tìm số cách tô thỏa mãn yêu cầu bài toán, vì đáp án khá lớn nên cần lấy mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa số nguyên \(N(1\leq N\leq 10^5)\)

• Dòng thứ hai chứa \(N-1\) cặp \(x_i,y_i(1\leq x_i,y_i\leq N)\). Và đề ra đảm bảo rằng đồ thị đã cho là cây.

Output

• In ra kết quả cần tìm

Example

3
1 2
2 3 

5

Cho hai xâu \(S\) và \(T\) chỉ gồm các chữ cái thường 'a'..'z'. Tìm độ xâu con chung dài nhất (subsequence) của hai xâu \(S\) và \(T\).

Input

• Gồm hai dòng
• Dòng thứ nhất chứa xâu \(S\).
• Dòng thứ hai chứa xâu \(T\).

Output

• In ra xâu con chung dài nhất của hai xâu \(S\) và \(T\). Nếu có nhiều xâu con dài nhất thoả mãn, in ra một xâu bất kì.
  Chú ý: Một xâu con của một xâu \(X\) bất kì thu được bằng cách xóa đi một vài kí tự (có thể không xóa kí tự nào) từ xâu \(X\) và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(|S|, |T| \le 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(|S|, |T| \le 10^4\).

Example

axyb
abyxb 

axb

Có lẽ ai cũng đã biết bài toán LONGEST COMMON SUBSEQUENCE. Vậy hôm nay có một bài toán khó hơn: In tất cả các xâu con chung dài nhất của hai xâu cho trước.

Input

• Gồm hai dòng là hai xâu \(A\) và \(B\). \((1 \leq |A|, |B| \leq 100)\).

Output

• Gồm nhiều dòng, mỗi dòng là một xâu con chung dài nhất của hai xâu \(A\) và \(B\) theo thứ tự từ điển.

Example

baadefg
aabedf 

aadf
aaef

Cho một dãy số nguyên \(A\) gồm \(N\) phần tử. Thực hiện xoá đi một vài phần tử của dãy \(A\), giữ nguyên vị trí tương đối của các phần tử còn lại ta thu được dãy \(C\). Khi đó \(C\) được gọi là dãy con của dãy \(A\). Dãy ban đầu cũng là dãy con của dãy \(A\).

Trong bài tập này bạn cần tính độ dài dãy \(C\) dài nhất thoả mãn điều kiện: \(C\) là dãy con của \(A\), \(C\) là dãy con của \(B\).

Input

• Dòng một là hai số nguyên \(M\) và \(N\) - theo thứ tự là độ dài dãy \(A\) và \(B\).

• Dòng thứ hai chứa dãy số nguyên \(A (1 ≤ A_i ≤ M)\). Các phần tử dãy \(A\) đôi một phân biệt.

• Dòng thứ ba chứa dãy số nguyên \(B ( 1 ≤ B_i ≤ N)\). Các phần tử dãy \(B\) đôi một phân biệt.

Output

• Ghi ra một số nguyên duy nhất là độ dài dãy \(C\) tìm được.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(M, N \leq 3.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(M, N \leq 10^5\).

Example

5 4
1 5 3 2 4
1 4 3 2 

3

Cho dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1,A_2,\cdots,A_N\) và dãy \(B\) gồm \(M\) phần tử gồm các số nguyên dương \(B_1,B_2,\cdots,B_M\). Dãy \(C\) được gọi là dãy con chung độ dài \(K\) của \(A,B\) nếu tồn tại hai dãy chỉ số như sau:

• \(1 \leq i_1 < i_2 < \cdots < i_K \leq N\).
• \(1 \leq j_1 < j_2 < \cdots < j_K \leq M\).
  Sao cho \(C_p = A_{i_p} = B_{j_p}\).

Yêu cầu: Tìm dãy \(C\) là dãy con chung của \(A,B\) sao cho độ dài \(K\) lớn nhất có thể.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N,M\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,\cdots,A_N (A_i \leq 10^6)\).
• Dòng thứ ba gồm \(M\) số nguyên dương \(B_1,B_2,\cdots,B_M (B_i \leq 10^6)\).

Output

• Dòng thứ nhất in ra số \(K\) là độ dài dãy con chung \(C\) dài nhất tìm được.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1,C_2,\cdots,C_K\). Nếu có nhiều dãy \(C\) thoả mãn, in ra một dãy bất kì.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3,M \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^3,M \leq 10^6\).

Nếu in ra đúng số \(K\) thì sẽ được 50% số điểm của test. Nếu in ra thêm được dãy \(C_1,C_2,\cdots,C_K\) mà đúng sẽ được thêm 50% số điểm của test

Example

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

7 
1 2 3 4 5 6 9

Ta gọi xâu \(R\) là xâu con của xâu \(S\) nếu ta có thể thu được xâu \(R\) bằng cách xoá đi một vài kí tự của xâu \(S\) và giữ nguyên thứ tự các kí tự còn lại.

Xâu \(C\) được gọi là xâu con chung của hai xâu \(A\) và \(B\) nếu \(C\) là xâu con của \(A\) và \(C\) là xâu con của \(B\). Đếm số lượng xâu con chung của hai xâu \(A\) và \(B\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 40)\).
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là số xâu con chung. Vì kết quả có thể rất lớn nên chỉ in kết quả khi lấy dư cho \(20071008\).

Example

1
abc
ab 

3

Cho hai xâu \(S\) và \(T\) chỉ gồm các ký tự in thường 'a' đến 'z'. Tìm độ dài xâu con chung không liền kề dài nhất (subsequence) của hai xâu \(S\) và \(T\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 40)\).
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là độ dài xâu con chung không liền kề dài nhất.

Example

1
abc
ab 

1

Cho hai xâu \(S\) và \(T\) chỉ gồm các ký tự in thường. Bạn được phép thực hiện một trong ba thao tác sau trên xâu \(S\):

• Chèn một ký tự bất kỳ vào xâu.
• Xoá một ký tự bất kỳ trong xâu.
• Thay đổi một ký tự bất kỳ trong xâu thành ký tự in thường khác.

Yêu cầu: Tìm số thao tác ít nhất để đưa xâu \(S\) về xâu \(T\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 40)\).
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\).

Output

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là số thao tác ít nhất.

Example

1
abc
ae 

2

Cho dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\) và dãy \(B\) gồm \(M\) phần tử gồm các số nguyên dương \(B_1, B_2, ..., B_M\). Dãy \(C\) được gọi là dãy con chung zigzag độ dài \(K\) của \(A, B\) nếu tồn tại hai dãy chỉ số như sau:

• \(1 \leq i_1 < i_2 < ... < i_K \leq N\).
• \(1 \leq j_1 < j_2 < ... < j_K \leq M\).

Sao cho \(C_p = A_{i_p} = B_{j_p}\) và thoả mãn một trong hai điều kiện sau:

• \(C_1 > C_2 < C_3 > ...\)
• \(C_1 < C_2 > C_3 < ...\)

Yêu cầu: Tìm dãy \(C\) là dãy con chung zigzag của \(A, B\) sao cho độ dài \(K\) lớn nhất có thể.

Input

• Gồm ba dòng:
• Dòng thứ nhất chứa hai số nguyên dương \(N, M\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^6)\).
• Dòng thứ ba gồm \(M\) số nguyên dương \(B_1, B_2, ..., B_M\) \((B_i \leq 10^6)\).

Output

• Gồm hai dòng:
• Dòng thứ nhất in ra số \(K\) là độ dài dãy con chung \(C\) dài nhất tìm được.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_K\). Nếu có nhiều dãy \(C\) thoả mãn, in ra một dãy bất kì.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, M \leq 10^2\).
• Subtask \(2\) (\(30\%\) số điểm): \(N, M \leq 10^3\).
• Subtask \(3\) (\(40\%\) số điểm): \(N, M \leq 5.10^3\).
• Nếu in ra đúng số \(K\) thì sẽ được \(50\%\) số điểm của test. Nếu in ra thêm được dãy \(C_1, C_2, ..., C_K\) mà đúng sẽ được thêm \(50\)% số điểm của test.

Example

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

5
4 6 5 8 7

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Đếm số dãy \(C\) thoả mãn \(K\) lớn nhất có thể, tức là đếm số dãy con tăng dài nhất.

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• In ra số dãy con tăng dài nhất. Vì kết quả có thể rất lớn nên chỉ in kết quả sau khi lấy dư \(20071008\).

Constraints

• \(N\leq 10^5\)
• \(|A_i| \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
2 3 5 4 

2

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Tìm dãy \(C\) sao cho độ dài \(K\) lớn nhất có thể. Nếu có nhiều dãy \(C\) thoả mãn, in ra dãy có thứ tự từ điển nhỏ nhất. Dãy \(C\) được gọi là dãy có thứ tự từ điển nhỏ hơn dãy \(C'\) nếu tồn tại chỉ số \(p\) \((p \geq 1)\) thoả mãn các điều kiện sau:

• \(C_1 = C'_1\), \(C_2 = C'_2\), \(...\), \(C_{p-1} = C'_{p-1}\) nếu \(p > 1\).
• \(C_p < C'_p\).

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• Dòng thứ nhất in ra số \(K\) là độ dài dãy con tăng \(C\) dài nhất.
• Dòng thứ hai in ra \(K\) số nguyên dương \(C_1, C_2, ..., C_N\) là dãy có thứ tự từ điển nhỏ nhất độ dài \(K\).

Constraints

• \(N \leq 10^5\)
• \(|A_i| \leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 3 5 4 6 

4
1 3 4 6

Một ngày, giáo sư Wu Zi Mu đã ra một bài tập mang tính "giải trí" cho các học sinh lớp \(1\) như sau:

"Cho \(N\) cái thùng chứa đựng đồ chơi, thùng thứ \(i\) chỉ chứa loại đồ chơi mang số \(C_i\), và có \(N-1\) con đường để di chuyển trực tiếp hai thùng đồ chơi. Đảm bảo rằng tồn tại đường đi duy nhất giữa hai thùng đồ chơi bất kỳ.

Ta định nghĩa \(D(u, v)\) là số loại đồ chơi khác nhau trên đường đi giữa hai thùng đồ chơi \(u\) và \(v\). Với mỗi thùng đồ chơi \(u\), giáo sư muốn tính toán \(Sum(u) = \sum\limits_{v=1}^N D(u, v)\).

Yêu cầu của các học sinh là xác định tất cả các \(Sum(u)\), với \(1 \leq u \leq N\)."

Học sinh rất là bối rối với bài tập này, không biết làm như thế nào cả. Các bạn giúp các học sinh thực hiện bài tập "giải trí" trên.

Input

• Gồm \(N + 1\) dòng:
• Dòng thứ nhất gồm số nguyên dương \(N\) là số thùng đồ chơi.
• Dòng thứ hai chứa \(N\) số nguyên dương \(C_1, C_2, C_3, ..., C_N\), với \(C_i\) là loại đồ chơi ở thùng thứ \(i\).
• \(N - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số \(u, v\) là có đường di chuyển trực tiếp giữa hai thùng đồ chơi \(u\) và \(v\).

Output

• Gồm \(N\) dòng, dòng thứ \(i\) chứa số nguyên dương duy nhất là kết quả \(Sum(i)\).

Scoring

• Trong tất cả các test, \(1 \leq C_i \leq 10^5\) với \(1 \leq i \leq N\).
• Có \(5\) subtasks:
• Subtask \(1\) (\(10\%\) số điểm): \(N \leq 3.10^2\).
• Subtask \(2\) (\(18\%\) số điểm): \(N \leq 5.10^3\).
• Subtask \(3\) (\(12\%\) số điểm): \(N \leq 10^5\), mọi thùng đều chứa cùng một loại đồ chơi.
• Subtask \(4\) (\(24\%\) số điểm): \(N \leq 10^5\), không tồn tại hai thùng khác nhau đều chứa cùng loại.
• Subtask \(5\) (\(36\%\) số điểm): \(N \leq 10^5\).

Example

5
1 2 3 2 1
1 2
1 4
2 3
2 5 

10
9
12
10
10

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Gọi \(SumC = \sum\limits_{i=1}^K C_i\). Tìm \(SumC\) lớn nhất có thể của dãy \(C\).

Input

• Dòng thứ nhất gồm số nguyên dương \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, A_3, ..., A_N\).

Output

• In ra một số nguyên dương duy nhất là kết quả bài toán.

Constraints

• \(N\leq 10^5\)
• \(A_i\leq 10^9\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2 3 5 4 

11

Cho một dãy \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con BeautiQ độ dài \(K\) của \(A\) nếu tồn tại dãy chỉ số thoả mãn các điều kiện như sau:

• \(K \geq 1\).
• \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
• \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
• \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\).
• \(GCD(C_1, C_2) > 1\), \(GCD(C_2, C_3) > 1\), \(...,\) \(GCD(C_{K-1}, C_K) > 1\) nếu \(K \geq 2\). (\(GCD\) tương ứng với \(UCLN\))

Yêu cầu: Tìm độ dài \(K\) lớn nhất có thể của dãy con BeautiQ \(C\).

Input

• Dòng thứ nhất chứa số nguyên dương \(N\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).

Output

• In ra số duy nhất là số nguyên dương \(K\).

Constraints

• \(N\leq 10^5\)
• \(A_i \leq 10^6\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^5\), \(A_i < A_{i+1}\) với \(\forall{i}, 1 \leq i < N\)
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm

Example

6
9 4 5 8 7 6 

2

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Input

• Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
• Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Output

• Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Example

6
1 2 5 4 6 2 

4

Có \(N\) bông hoa được sắp thành \(1\) hàng. Với mỗi \(i(1\le i\le N)\), chiều cao và độ "đẹp" của bông hoa thứ \(i\) lần lượt là \(h_i\) và \(a_i\). Ở đây \(h_1,h_2,...,h_N\) phân biệt với nhau từng đôi một!

\(Kaninho\) muốn lấy đi vài bông hoa để những bông hoa còn lại thỏa mãn điều kiện sau :

• Chiều cao của những bông hoa còn lại là một dãy đơn điều tăng dần từ trái sang phải

Yêu cầu: Tìm độ "đẹp" lớn nhất có thể có của những bông hoa còn lại

Input

• Dòng thứ nhất chứa số nguyên \(N(1\le N\le 2\times 10^5)\)

• Dòng thứ hai chứa \(n\) số nguyên \(h_1,h_2,...,h_N(1\le h_i\le N)\)

• Dòng thứ ba chứa \(n\) số nguyên \(a_1,a_2,...,a_N(1\le a_i\le 10^9)\)

Output

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

Example

4
3 1 4 2
10 20 30 40

60

Cho một đồ thị đơn, có hướng \(G\) với \(N\) đỉnh, được đánh số \(1,2,3,4,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), bạn được cho \(1\) số nguyên \(a_{i,j}\) thể hiện sự kết nối có hướng giữa hai đỉnh \(i\) và \(j\). Nếu \(a_{i,j}=1\) thì đỉnh \(i\) được nối với đỉnh \(j\) theo chiều từ \(i\) đến \(j\), nếu \(a_{i,j}=0\) thì không tồn tại kết nối giữa hai đỉnh \(i,j\).

Yêu cầu: Tìm số đường khác nhau có độ dài là \(K\) trong \(G\), biết rằng mỗi con đường này có thể đi qua một cạnh nhiều lần.

Vì đáp số có thể lớn nên cần lấy mod \(10^9+7\) trước khi in ra

Input

• Dòng thứ nhất chứa hai số nguyên \(N,K(1\le N\le 50,1\le K\le 10^{18})\)

• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,n}(1\le i\le N, a_{i,j}\in \left\{0,1\right\})\)

Output

• In ra đáp án sau khi đã lấy mod \(10^9+7\)

Example

3 3
0 1 0
1 0 1
0 0 0

3

Tìm số các số nguyên dương từ \(1\) đến \(K\) thỏa mãn tổng các chữ số của nó là bội của \(D\).

Vì đáp án có thể lớn nên cần lấy mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa số nguyên \(K\)
• Dòng thứ hai chứa số nguyên \(D\)

Output

• In ra kết quả cần tìm sau khi đã lấy mod \(10^9+7\)

Constraints

• \(1<K<10^{10000}\)
• \(1\le D\le 100\)

Example

30
4 

6

Cho số nguyên dương \(N\). Bạn được cho xâu \(s\) có độ dài là \(N-1\), chỉ gồm hai kí tự \('>','<'\).

Tìm số lượng hoán vị \((p_1,p_2,...,p_N)\) của \((1,2,3,...,N)\) thỏa mãn điều kiện sau:

Với mỗi \(i(1\le i\le N-1),p_i<p_{i+1}\) nếu kí tự thứ \(i\) trong \(s\) là \('<'\) và \(p_i>p_{i+1}\) nếu kí tự thứ \(i\) của xâu \(s\) là \('>'\).

Vì đáp án có thể rất lớn nên cần lấy mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa số nguyên \(N\)
• Dòng thứ hai chứa xâu \(s\) có độ dài là \(N-1\)

Output

• In ra đáp án cần tìm sau khi đã lấy mod \(10^9+7\)

Constraints

• \(2\le N\le 3000\)

Example

4
<>< 

5

Có \(N\) con thỏ được đánh số \(1,2,3,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), độ "tâm đầu ý hợp" của con thỏ \(i\) và \(j\) được kí hiệu bởi một số nguyên \(a_{i,j}\). Ở đây \(a_{i,i}=0\) với mọi \(i(1\le i\le N),a_{j,i}=a_{i,j}\) với mọi \(i,j(1\le i,j\le N)\).

\(Kaninho\) chia \(N\) con thỏ này thành nhiều nhóm. Ở đây, mỗi con thỏ thuộc về chính xác \(1\) nhóm. Sau khi chia xong, với mỗi cặp \(i,j(1\le i<j\le N)\). \(Kaninho\) sẽ kiếm được \(a_{i,j}\) điểm nếu con thỏ \(i\) và \(j\) cùng thuộc về một nhóm.

Tìm số điểm tối đa mà \(Kaninho\) có thể thu được.

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,N}\) thể hiện độ "tâm đầu ý hợp" của những chú thỏ với nhau.

Output

• In ra kết quả cần tìm.

Constraints

• \(1\le i\le N,|a_{i,j}|\le 10^9\)
• \(1\le N\le 16\)

Example

3
0 10 20
10 0 -100
20 -100 0 

20

Trong siêu thị có \(N\) đồ vật, đồ vật thứ \(i\) có khối lượng là \(W_i\), và có giá trị là \(V_i\). Một ngày, CJ vào siêu thị để mua đồ. Vì trước kia mua nhiều ở đây, nên CJ được một tấm thẻ đặc biệt của siêu thị. Khi có tấm thẻ này thì CJ được quyền lấy một số món đồ sao cho tổng khối lượng không quá \(M\). Vì CJ không giỏi tính toán, nên các bạn hãy giúp CJ lấy một số món đồ sao cho tổng khối lượng không quá \(M\), và tổng giá trị lớn nhất có thể.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N, M\) là số món đồ trong siêu thị và tổng khối lượng tối đa trong tấm thẻ.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\), \(V_i\) lần lượt là khối lượng và giá trị của đồ vật thứ \(i\).

Output

• Dòng thứ nhất in ra số món đồ mà CJ lấy để tổng giá trị đạt lớn nhất.
• Dòng thứ hai in ra chỉ số các món đồ mà CJ lấy theo thứ tự tăng dần.

Constants

• \(N \leq 18, M \leq 5.10^9\)
• \(W_i, V_i \leq 10^9\), với \(\forall i, 1 \leq i \leq N\).

Example

5 20
7 1
5 8
1 1
7 8
9 7

4
1 2 3 4

Trong siêu thị có \(N\) đồ vật, đồ vật thứ \(i\) có khối lượng là \(W_i\), và có giá trị là \(V_i\). Một ngày, CJ vào siêu thị để mua đồ. Vì trước kia mua nhiều ở đây, nên CJ được một tấm thẻ đặc biệt của siêu thị. Khi có tấm thẻ này thì CJ được quyền lấy một số món đồ sao cho tổng khối lượng không quá \(M\). Vì CJ không giỏi tính toán, nên các bạn hãy giúp CJ lấy một số món đồ sao cho tổng khối lượng không quá \(M\), và tổng giá trị lớn nhất có thể.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N, M\) là số món đồ trong siêu thị và tổng khối lượng tối đa trong tấm thẻ.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\), \(V_i\) lần lượt là khối lượng và giá trị của đồ vật thứ \(i\).

Output

• Dòng thứ nhất in ra số món đồ mà CJ lấy để tổng giá trị đạt lớn nhất.
• Dòng thứ hai in ra chỉ số các món đồ mà CJ lấy theo thứ tự tăng dần.

Scoring

• \(M \leq 15.10^9\), \(W_i, V_i \leq 10^9\), với \(\forall i, 1 \leq i \leq N\).
• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 18\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 36\).

Example

5 20
7 1
5 8
1 1
7 8
9 7

4
1 2 3 4

Trong siêu thị có \(N\) đồ vật, đồ vật thứ \(i\) có khối lượng là \(W_i\), và có giá trị là \(V_i\). Một ngày, CJ vào siêu thị để mua đồ. Vì trước kia mua nhiều ở đây, nên CJ được một tấm thẻ đặc biệt của siêu thị. Khi có tấm thẻ này thì CJ được quyền lấy một số món đồ sao cho tổng khối lượng phải nằm trong giới hạn từ \(L\) tới \(R\). Vì CJ không giỏi tính toán, nên các bạn hãy giúp CJ lấy một số món đồ sao cho tổng khối lượng phải từ \(L\) tới \(R\), và tổng giá trị lớn nhất có thể.

Input

• Dòng thứ nhất chứa ba số nguyên dương \(N, L, R\) là số món đồ trong siêu thị và giới hạn tổng khối lượng mà CJ phải lấy.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\), \(V_i\) lần lượt là khối lượng và giá trị của đồ vật thứ \(i\).

Output

• Dòng thứ nhất in ra số món đồ mà CJ lấy để tổng giá trị đạt lớn nhất.
• Dòng thứ hai in ra chỉ số các món đồ mà CJ lấy theo thứ tự tăng dần.

Constants

• \(1 \leq L \leq R \leq 15.10^9\), \(W_i, V_i \leq 10^9\), với \(\forall i, 1 \leq i \leq N\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 18\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 36\).

Example

3 1 8
3 1
4 3
8 2

2
1 2

algorit oai hùng ngày nào nay đã trở thành bảo vệ của rừng AnLuuLand (có dạng hình chữ nhật kích thước \(M * N\)). Để đền đáp công lao to lớn của algorit, Chúa đất cho phép anh chọn một vùng đất hình chữ nhật có kích thước \(k * k\), có các cạnh song song với các bìa rừng, khai thác tài nguyên tại vùng đất này để lây kinh phí dựng nhà và lấy vợ.

Chúa đất chỉ cho phép anh khai thác cây trong đúng vùng đất mà anh ấy chọn. Biết giá trị của mỗi cây trong khu rừng AnLuuLand tại vị trí dòng \(i\) cột \(j\) là \(a_{ij}\) nguyên. Bạn hãy giúp algorit chọn một vùng đất có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất.

Input

• Dòng 1: Gồm 3 số \(m, n , k ( 1 ≤ k ≤ m, n ≤ 1000).\)

• \(m\) dòng sau mỗi dòng \(n\) số nguyên là giá trị của mỗi cây trong khu rừng. Giá trị của mỗi cây là một số nguyên có trị tuyệt đối không quá \(10^9.\)

Output

• Một số duy nhất là giá trị cao nhất mà algorit có thể nhận được.

Scoring

• \(a_{ij} \leq |10^9|\)
• Subtask \(1\) (\(20\%\) số điểm): \(n, m\) \(\leq 10\)
• Subtask \(2\) (\(20\%\) số điểm): \(n, m\) \(\leq 60\)
• Subtask \(3\) (\(20\%\) số điểm): \(n, m\) \(\leq 400\)
• Subtask \(4\) (\(40\%\) số điểm):\(n, m\) \(\leq 1000\)

Example

4 5 2
1 1 2 0 0
1 2 1 0 1
4 3 5 1 1
1 5 5 0 0 

18

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1 cm\). Mỗi tuần chúa đất ra lệnh bón phân cho một khu hình chữ nhật: \((x, y, u, v, c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\) thêm \(c\) (gr) phân bón. Mỗi cây xanh khi nhận được \(1\) (gr) phân bón sẽ cao thêm \(1 (cm).\)

Sau \(k\) tuần chúa đất muốn biết tình trạng độ cao của cây xanh trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng 1: Gồm 3 số \(m, n , k (1 \leq m, n \leq 1000, 1 \le k \le 10^5).\)

• \(k\) dòng sau, mỗi dòng gồm 5 số nguyên \((x,y,u,v,c)\) là một yêu cầu bón phân của chúa đất. \((1 \le x, u \le m, 1 \le y, v \le n, 1 \le c \le 10^6)\)

Output

• In ra \(m\) dòng, mỗi dòng gồm \(n\) số nguyên cách nhau một dấu cách là tình trạng độ cao cây của khu rừng sau \(k\) tuần được bón phân.

Example

4 5 3
1 1 4 5 1
1 1 2 2 2
1 2 1 4 3

4 7 5 5 2
4 4 2 2 2
2 2 2 2 2
2 2 2 2 2