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

Ban đầu, một con ếch đứng ở hòn đá ~1~. Từ hòn đá ~i~, ếch chỉ có thể nhảy đến hòn đá ~i+1~ hoặc ~i+2~ (nếu tồn tại). Khi nhảy từ hòn đá ~i~ sang hòn đá ~j~, chi phí phát sinh là ~|h_i - h_j|~.

Yêu cầu

Hãy tìm tổng chi phí nhỏ nhất để ếch đi từ hòn đá ~1~ đến hòn đá ~N~.

Dữ liệu

• Dòng đầu chứa số nguyên ~N~.
• Dòng thứ hai chứa ~N~ số nguyên ~h_1, h_2, \ldots, h_N~.

Kết quả

• In ra một số nguyên: tổng chi phí nhỏ nhất để ếch đến được hòn đá ~N~.

Ví dụ

Ví dụ 1

Input

4
10 30 40 20

Output

30

Ví dụ 2

Input

2
10 10

Output

0

Ví dụ 3

Input

6
30 10 60 10 60 50

Output

40

Giải thích

Ví dụ 1

Chọn đường đi ~1~ → ~2~ → ~4~, chi phí là ~|10-30| + |30-20| = 30~.

Ví dụ 2

Chỉ có thể đi ~1~ → ~2~, chi phí là ~|10-10| = 0~.

Ví dụ 3

Chọn đường đi ~1~ → ~3~ → ~5~ → ~6~, chi phí là ~|30-60| + |60-60| + |60-50| = 40~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~2 \le N \le 10^5~
• ~1 \le h_i \le 10^4~

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

Ban đầu, một con ếch đứng ở hòn đá ~1~. Khi đang ở hòn đá ~i~, ếch có thể nhảy đến một trong các hòn đá ~i+1~, ~i+2~, ..., ~i+K~ (chỉ những hòn đá có chỉ số không vượt quá ~N~).
Nếu ếch nhảy từ hòn đá ~i~ sang hòn đá ~j~ thì chi phí là ~|h_i - h_j|~.

Yêu cầu

Tính tổng chi phí nhỏ nhất để ếch đi từ hòn đá ~1~ đến hòn đá ~N~.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~K~.
• Dòng 2: ~N~ số nguyên ~h_1, h_2, \ldots, h_N~.

Kết quả

• In ra một số nguyên: tổng chi phí nhỏ nhất để ếch đến được hòn đá ~N~.

Ví dụ

Ví dụ 1

Input

5 3
10 30 40 50 20

Output

30

Ví dụ 2

Input

3 1
10 20 10

Output

20

Ví dụ 3

Input

2 100
10 10

Output

0

Ví dụ 4

Input

10 4
40 10 20 70 80 10 20 70 80 60

Output

40

Giải thích

Ví dụ 1

Chọn đường đi ~1~ → ~2~ → ~5~, chi phí ~|10-30| + |30-20| = 30~.

Ví dụ 2

Do ~K=1~ nên chỉ đi được ~1~ → ~2~ → ~3~, chi phí ~|10-20| + |20-10| = 20~.

Ví dụ 3

Đi ~1~ → ~2~, chi phí ~|10-10| = 0~.

Ví dụ 4

Một cách tối ưu: ~1~ → ~4~ → ~8~ → ~10~, chi phí ~|40-70| + |70-70| + |70-60| = 40~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~2 \le N \le 10^5~
• ~1 \le K \le 100~
• ~1 \le h_i \le 10^4~

Kì nghỉ hè của Ánh kéo dài ~N~ ngày. Mỗi ngày ~i~ (~1 \le i \le N~), Ánh chọn đúng một trong ba hoạt động:

• ~A~: nhận ~a_i~ điểm hạnh phúc
• ~B~: nhận ~b_i~ điểm hạnh phúc
• ~C~: nhận ~c_i~ điểm hạnh phúc

Do dễ chán, Ánh không được thực hiện cùng một hoạt động trong hai ngày liên tiếp.

Yêu cầu

Tính tổng điểm hạnh phúc lớn nhất mà Ánh có thể đạt được sau ~N~ ngày.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• ~N~ dòng tiếp theo, dòng ~i~ gồm ba số nguyên ~a_i~, ~b_i~, ~c_i~.

Kết quả

• In ra một số nguyên: tổng điểm hạnh phúc lớn nhất.

Ví dụ

Ví dụ 1

Input

3
10 40 70
20 50 80
30 60 90

Output

210

Ví dụ 2

Input

1
100 10 1

Output

100

Ví dụ 3

Input

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

Output

46

Giải thích

Ví dụ 1

Chọn theo thứ tự ~C, B, C~ thì tổng là ~70 + 50 + 90 = 210~.

Ví dụ 2

Chỉ có ~1~ ngày, chọn hoạt động ~A~ được ~100~.

Ví dụ 3

Một phương án tối ưu: ~C, A, B, A, C, B, A~, tổng bằng ~46~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 10^5~
• ~1 \le a_i, b_i, c_i \le 10^4~

Có ~N~ món đồ, được đánh số từ ~1~ đến ~N~. Món đồ thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~.

Taro muốn chọn một số món đồ bỏ vào ba lô. Ba lô có sức chứa ~W~, nghĩa là tổng khối lượng các món được chọn không vượt quá ~W~.

Yêu cầu

Hãy tìm tổng giá trị lớn nhất mà Taro có thể mang về.

Dữ liệu

• Dòng ~1~: hai số nguyên ~N~ và ~W~.
• ~N~ dòng tiếp theo: dòng ~i~ gồm hai số nguyên ~w_i~ và ~v_i~.

Kết quả

• In ra một số nguyên: tổng giá trị lớn nhất có thể đạt được.

Ví dụ

Ví dụ 1

Input

3 8
3 30
4 50
5 60

Output

90

Ví dụ 2

Input

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Output

5000000000

Ví dụ 3

Input

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output

17

Giải thích

Ví dụ 1

Chọn món ~1~ và ~3~: tổng khối lượng ~3+5=8~, tổng giá trị ~30+60=90~.

Ví dụ 2

Vì ~W=5~ và có ~5~ món đều có ~w_i=1~, chọn cả ~5~ món được tổng giá trị ~5 \cdot 10^9~.

Ví dụ 3

Chọn các món ~2~, ~4~, ~5~: tổng khối lượng ~5+6+3=14 \le 15~, tổng giá trị ~6+6+5=17~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 100~
• ~1 \le W \le 10^5~
• ~1 \le w_i \le W~
• ~1 \le v_i \le 10^9~

Có ~N~ món đồ, đánh số từ ~1~ đến ~N~. Món đồ thứ ~i~ có khối lượng ~w_i~ và giá trị ~v_i~.

Taro muốn chọn một số món đồ bỏ vào ba lô. Ba lô có sức chứa ~W~, nghĩa là tổng khối lượng các món được chọn không vượt quá ~W~.

Yêu cầu

Tìm tổng giá trị lớn nhất mà Taro có thể mang về.

Dữ liệu

• Dòng ~1~: hai số nguyên ~N~ và ~W~.
• ~N~ dòng tiếp theo: dòng ~i~ gồm hai số nguyên ~w_i~ và ~v_i~.

Kết quả

• In ra một số nguyên: tổng giá trị lớn nhất có thể đạt được.

Ví dụ

Ví dụ 1

Input

3 8
3 30
4 50
5 60

Output

90

Ví dụ 2

Input

1 1000000000
1000000000 10

Output

10

Ví dụ 3

Input

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Output

17

Giải thích

Ví dụ 1

Chọn món ~1~ và ~3~: tổng khối lượng ~3+5=8~, tổng giá trị ~30+60=90~.

Ví dụ 2

Chỉ có thể chọn món ~1~, tổng giá trị ~10~.

Ví dụ 3

Chọn các món ~2~, ~4~, ~5~: tổng khối lượng ~5+6+3=14 \le 15~, tổng giá trị ~6+6+5=17~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 100~
• ~1 \le W \le 10^9~
• ~1 \le w_i \le W~
• ~1 \le v_i \le 10^3~

Bạn được cho hai xâu ~s~ và ~t~ (chỉ gồm các chữ cái tiếng Anh thường).

Một dãy con (subsequence) của xâu ~x~ là xâu thu được bằng cách xoá đi 0 hoặc nhiều ký tự của ~x~ và giữ nguyên thứ tự các ký tự còn lại.

Yêu cầu

Hãy in ra một xâu dài nhất sao cho nó là dãy con của cả ~s~ và ~t~ (tức là LCS của ~s~ và ~t~).
Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu

• Dòng 1: xâu ~s~
• Dòng 2: xâu ~t~

Kết quả

• In ra một xâu là dãy con chung dài nhất của ~s~ và ~t~ (có thể là xâu rỗng).

Ví dụ

Ví dụ 1

Input

axyb
abyxb

Output

axb

Ví dụ 2

Input

a
z

Output

Giải thích

Ví dụ 1

~axb~ là dãy con của ~axyb~ (lấy ~a, x, b~) và cũng là dãy con của ~abyxb~ (lấy ~a, x, b~). Đây là một LCS hợp lệ.

Ví dụ 2

Hai xâu ~a~ và ~z~ không có ký tự chung, nên LCS là xâu rỗng.

Ràng buộc và chấm điểm

Ràng buộc

• ~s~ và ~t~ chỉ gồm chữ cái thường.
• ~1 \le |s|, |t| \le 3000~

Cho một lưới gồm ~H~ hàng và ~W~ cột. Ô ở hàng ~i~ (tính từ trên xuống) và cột ~j~ (tính từ trái sang) được ký hiệu là ~(i,j)~.

Mỗi ô ~(i,j)~ được mô tả bởi ký tự ~a_{i,j}~:

• Nếu ~a_{i,j} = '.'~ thì đó là ô trống (đi được).
• Nếu ~a_{i,j} = '\#'~ thì đó là ô tường (không đi được).

Biết rằng hai ô ~(1,1)~ và ~(H,W)~ đều là ô trống.

Taro bắt đầu từ ~(1,1)~ và muốn tới ~(H,W)~ bằng cách lặp lại việc di chuyển sang phải hoặc xuống đúng 1 ô, và chỉ được đi vào ô trống.

Yêu cầu

Hãy tính số lượng đường đi từ ~(1,1)~ đến ~(H,W)~.
Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho ~10^9 + 7~.

Dữ liệu

• Dòng 1: hai số nguyên ~H~ và ~W~.
• ~H~ dòng tiếp theo: mỗi dòng là một xâu độ dài ~W~ gồm . và #, mô tả lưới.

Kết quả

• In ra một số nguyên: số đường đi từ ~(1,1)~ đến ~(H,W)~ theo modulo ~10^9 + 7~.

Ví dụ

Ví dụ 1

Input

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

Output

3

Ví dụ 2

Input

5 2
..
#.
..
.#
..

Output

0

Giải thích

Ví dụ 1

Có đúng ~3~ cách đi hợp lệ từ ~(1,1)~ tới ~(3,4)~ do một số ô bị chặn bởi tường.

Ví dụ 2

Không tồn tại đường đi nào từ ~(1,1)~ đến ~(5,2)~ nên kết quả là ~0~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le H, W \le 1000~
• ~a_{i,j} \in \{'.', '\#'\}~
• ~(1,1)~ và ~(H,W)~ là ô trống.

Có ~N~ đồng xu. Với mỗi đồng xu ~i~, khi tung lên thì xác suất ra mặt ngửa là ~p_i~ (và xác suất ra mặt sấp là ~1 - p_i~). Các lần tung là độc lập.

Gọi ~X~ là số đồng xu ra mặt ngửa sau khi tung cả ~N~ đồng.

Yêu cầu

Tính xác suất để số mặt ngửa nhiều hơn số mặt sấp, tức là:

• ~X > N - X~ (hay tương đương ~X > \lfloor N/2 \rfloor~).

Dữ liệu

• Dòng 1: số nguyên ~N~.
• Dòng 2: ~N~ số thực ~p_1, p_2, \ldots, p_N~.

Kết quả

• In ra một số thực: xác suất cần tìm.
• Sai số tuyệt đối hoặc tương đối không vượt quá ~10^{-9}~.

Ví dụ

Ví dụ 1

Input

3
0.30 0.60 0.80

Output

0.612

Giải thích

Ví dụ 1

Cần xác suất ~X \ge 2~ (vì ~N=3~). Ta có:

• ~P(X=2)=0.3\cdot0.6\cdot(1-0.8)+0.3\cdot(1-0.6)\cdot0.8+(1-0.3)\cdot0.6\cdot0.8=0.468~
• ~P(X=3)=0.3\cdot0.6\cdot0.8=0.144~ Tổng ~=0.612~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 3000~
• ~0 \le p_i \le 1~
• ~p_i~ là số thực.

Có ~N~ cái đĩa sushi, đánh số từ ~1~ đến ~N~. Ban đầu, đĩa thứ ~i~ có ~a_i~ miếng sushi, với ~1 \le a_i \le 3~.

Hiếu sẽ lặp lại thao tác sau cho đến khi ăn hết tất cả sushi:

• Chọn ngẫu nhiên đều một số ~i~ trong ~\{1,2,\dots,N\}~.
• Nếu đĩa ~i~ còn sushi thì ăn 1 miếng; nếu đĩa ~i~ đã rỗng thì không làm gì.

Yêu cầu

Hãy tính kỳ vọng số lần thao tác cần thực hiện cho đến khi tất cả sushi được ăn hết.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \ldots, a_N~.

Kết quả

• In ra một số thực: kỳ vọng cần tìm.
• Kết quả được chấp nhận nếu sai số tương đối không vượt quá ~10^{-9}~.

Ví dụ

Ví dụ 1

Input

3
1 1 1

Output

5.5

Ví dụ 2

Input

1
3

Output

3

Giải thích

Ví dụ 1

Kỳ vọng số lần thao tác để ăn miếng đầu tiên là ~1~.
Sau đó còn ~2~ đĩa có sushi nên kỳ vọng để ăn tiếp 1 miếng là ~\frac{3}{2}=1.5~.
Cuối cùng còn ~1~ đĩa có sushi nên kỳ vọng là ~3~.
Tổng ~1 + 1.5 + 3 = 5.5~.

Ví dụ 2

Vì chỉ có ~1~ đĩa, mỗi lần thao tác đều ăn được 1 miếng cho đến khi hết, nên cần đúng ~3~ lần.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 300~
• ~1 \le a_i \le 3~

Hiếu và Hoàng chơi một trò chơi với một đống đá.

Cho tập ~A=\{a_1,a_2,\ldots,a_N\}~ gồm ~N~ số nguyên dương. Ban đầu đống có ~K~ viên đá. Hai người chơi lần lượt thực hiện nước đi, Hiếu đi trước:

• Chọn một giá trị ~x~ thuộc ~A~ và lấy đúng ~x~ viên đá khỏi đống.

Người chơi thua nếu đến lượt mình mà không thể đi (tức là không tồn tại ~x \in A~ sao cho ~x \le~ số đá hiện có).

Yêu cầu

Giả sử cả hai chơi tối ưu, hãy xác định người chiến thắng.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~K~.
• Dòng 2: ~N~ số nguyên ~a_1,a_2,\ldots,a_N~.

Kết quả

• Nếu Hiếu thắng, in ra First.
• Nếu Hoàng thắng, in ra Second.

Ví dụ

Ví dụ 1

Input

2 4
2 3

Output

First

Ví dụ 2

Input

2 5
2 3

Output

Second

Ví dụ 3

Input

1 100000
1

Output

Second

Giải thích

Ví dụ 1

Hiếu lấy ~3~ viên, còn ~1~ viên nên Hoàng không thể lấy được ~2~ hay ~3~ → Hoàng thua.

Ví dụ 2

Dù Hiếu lấy ~2~ hay ~3~ viên thì Hoàng đều có nước đi đối ứng để đưa Hiếu về trạng thái thua.

Ví dụ 3

Mỗi lượt chỉ có thể lấy ~1~ viên. Vì ~K=100000~ là chẵn nên người đi sau lấy viên cuối cùng → Hiếu thua.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 100~
• ~1 \le K \le 10^5~
• ~1 \le a_1 < a_2 < \cdots < a_N \le K~

Hiếu và Hoàng chơi một trò chơi với một dãy số.

Ban đầu có dãy ~a=(a_1,a_2,\ldots,a_N)~. Hai người thay phiên nhau thực hiện nước đi, Hiếu đi trước. Khi dãy chưa rỗng, người chơi ở lượt của mình sẽ:

• Lấy phần tử đầu hoặc phần tử cuối của dãy và nhận đúng số điểm bằng giá trị phần tử vừa lấy.

Trò chơi kết thúc khi dãy rỗng. Gọi ~X~ là tổng điểm của Hiếu và ~Y~ là tổng điểm của Hoàng.
Hiếu muốn ~X-Y~ là lớn nhất, còn Hoàng muốn ~X-Y~ nhỏ nhất.

Yêu cầu

Giả sử cả hai chơi tối ưu, hãy tính giá trị cuối cùng của ~X-Y~.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• Dòng 2: ~N~ số nguyên ~a_1,a_2,\ldots,a_N~.

Kết quả

• In ra một số nguyên: giá trị ~X-Y~ khi hai người chơi tối ưu.

Ví dụ

Ví dụ 1

Input

4
10 80 90 30

Output

10

Ví dụ 2

Input

3
10 100 10

Output

-80

Ví dụ 3

Input

1
10

Output

10

Giải thích

Ví dụ 1

Một cách chơi tối ưu:

• Hiếu lấy ~30~, Hoàng lấy ~90~, Hiếu lấy ~80~, Hoàng lấy ~10~.
  Khi đó ~X=30+80=110~, ~Y=90+10=100~, nên ~X-Y=10~.

Ví dụ 2

Nếu Hiếu lấy một đầu ~10~, Hoàng sẽ lấy ~100~ ở lượt sau. Kết quả tối ưu là ~X-Y=-80~.

Ví dụ 3

Chỉ có một phần tử nên Hiếu lấy được ~10~, do đó ~X-Y=10~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 3000~
• ~1 \le a_i \le 10^9~

Có ~N~ đứa trẻ được đánh số từ ~1~ đến ~N~. Các em muốn chia đều hết ~K~ viên kẹo.

Với mỗi đứa trẻ ~i~, số kẹo mà em đó nhận được phải nằm trong đoạn ~[0, a_i]~.

Hai cách chia được xem là khác nhau nếu tồn tại một trẻ nhận số kẹo khác nhau giữa hai cách.

Yêu cầu

Hãy đếm số cách chia sao cho ~x_1 + x_2 + \cdots + x_N = K~ và ~0 \le x_i \le a_i~ với mọi ~i~.
In kết quả theo modulo ~10^9+7~.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~K~.
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \ldots, a_N~.

Kết quả

• In ra số cách chia kẹo, lấy modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

3 4
1 2 3

Output

5

Ví dụ 2

Input

1 10
9

Output

0

Ví dụ 3

Input

2 0
0 0

Output

1

Ví dụ 4

Input

4 100000
100000 100000 100000 100000

Output

665683269

Giải thích

Ví dụ 1

Có đúng ~5~ cách:
~(0,1,3), (0,2,2), (1,0,3), (1,1,2), (1,2,1)~.

Ví dụ 2

Vì ~a_1=9 < K=10~ nên không thể chia hết ~10~ viên kẹo.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 100~
• ~0 \le K \le 10^5~
• ~0 \le a_i \le K~

Có ~N~ viên bột được xếp thành một hàng theo thứ tự từ trái sang phải. Khối lượng của viên bột thứ ~i~ là ~a_i~.

Bạn sẽ lặp lại thao tác sau cho đến khi chỉ còn đúng một viên bột:

• Chọn hai viên bột kề nhau và nhào chúng lại thành một viên bột mới.
  Chi phí của lần nhào này bằng tổng khối lượng của hai viên bột được nhào.

Sau khi nhào, viên bột mới sẽ nằm đúng vị trí của cặp vừa chọn (tức là xoá hai viên đó và chèn viên mới vào vị trí ấy, giữ nguyên thứ tự các viên còn lại).

Yêu cầu

Hãy tìm tổng chi phí nhỏ nhất để nhào tất cả các viên bột thành một viên duy nhất.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• Dòng 2: ~N~ số nguyên ~a_1, a_2, \ldots, a_N~.

Kết quả

• In ra một số nguyên: tổng chi phí nhỏ nhất.

Ví dụ

Ví dụ 1

Input

4
10 20 30 40

Output

190

Ví dụ 2

Input

5
10 10 10 10 10

Output

120

Giải thích

Ví dụ 1

Một cách tối ưu:

• Nhào ~10~ và ~20~ → chi phí ~30~, dãy thành ~30 30 40~
• Nhào ~30~ và ~30~ → chi phí ~60~, dãy thành ~60 40~
• Nhào ~60~ và ~40~ → chi phí ~100~, dãy thành ~100~
  Tổng chi phí ~30 + 60 + 100 = 190~.

Ví dụ 2

Một cách tối ưu:

• ~10 10 10 10 10~ → ~20 10 10 10~ (chi phí ~20~)
• → ~20 20 10~ (chi phí ~20~)
• → ~20 30~ (chi phí ~30~)
• → ~50~ (chi phí ~50~)
  Tổng ~20+20+30+50=120~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~2 \le N \le 400~
• ~1 \le a_i \le 10^9~
• Lưu ý: đáp án có thể không vừa kiểu ~\text{32-bit}.~

Có ~N~ nam và ~N~ nữ, đều được đánh số từ ~1~ đến ~N~.

Với mọi ~i, j~ ~(1 \le i, j \le N)~, mức hợp nhau của nam ~i~ và nữ ~j~ được cho bởi số nguyên ~a_{i,j}~:

• ~a_{i,j}=1~: hai người hợp nhau.
• ~a_{i,j}=0~: hai người không hợp nhau.

Bạn cần ghép thành đúng ~N~ cặp, mỗi cặp gồm 1 nam + 1 nữ hợp nhau, và mỗi người thuộc đúng 1 cặp.

Yêu cầu

Hãy tính số cách ghép thỏa mãn, lấy modulo ~10^9+7~.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• ~N~ dòng tiếp theo: mỗi dòng gồm ~N~ số ~a_{i,1}, a_{i,2}, \ldots, a_{i,N}~.

Kết quả

• In ra số cách ghép, modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

3
0 1 1
1 0 1
1 1 1

Output

3

Ví dụ 2

Input

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Output

1

Giải thích

Ví dụ 1

Có ~3~ cách ghép hợp lệ (ký hiệu ~(i,j)~ là cặp nam ~i~ với nữ ~j~):

• ~(1,2), (2,1), (3,3)~
• ~(1,2), (2,3), (3,1)~
• ~(1,3), (2,1), (3,2)~

Ví dụ 2

Chỉ có đúng ~1~ cách ghép: ~(1,2), (2,4), (3,1), (4,3)~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 21~
• ~a_{i,j} \in \{0,1\}~

Có ~N~ bông hoa xếp thành một hàng. Với mỗi ~i~ ~(1 \le i \le N)~, bông hoa thứ ~i~ (từ trái sang phải) có:

• chiều cao ~h_i~
• độ đẹp ~a_i~

Biết rằng ~h_1, h_2, \ldots, h_N~ đôi một khác nhau.

Taro sẽ nhổ bớt một số bông sao cho các bông còn lại (giữ nguyên thứ tự ban đầu) có chiều cao không giảm từ trái sang phải. Do các ~h_i~ đều khác nhau, điều này tương đương chiều cao tăng dần.

Yêu cầu

Hãy tìm tổng độ đẹp lớn nhất có thể của các bông còn lại.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• Dòng 2: ~N~ số nguyên ~h_1, h_2, \ldots, h_N~.
• Dòng 3: ~N~ số nguyên ~a_1, a_2, \ldots, a_N~.

Kết quả

• In ra một số nguyên: tổng độ đẹp lớn nhất.

Ví dụ

Ví dụ 1

Input

4
3 1 4 2
10 20 30 40

Output

60

Ví dụ 2

Input

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

Output

31

Giải thích

Ví dụ 1

Giữ bông thứ ~2~ và ~4~: chiều cao ~1,2~ tăng dần, tổng độ đẹp ~20+40=60~.

Ví dụ 2

Một cách tối ưu là giữ các bông thứ ~2,3,6,8,9~; tổng độ đẹp bằng ~31~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 2 \cdot 10^5~
• ~1 \le h_i \le N~
• ~h_1, h_2, \ldots, h_N~ đôi một khác nhau.
• ~1 \le a_i \le 10^9~

Bạn được cho hai số nguyên ~K~ và ~D~. Trong đó ~K~ có thể rất lớn nên được cho dưới dạng xâu thập phân (không có chữ số 0 ở đầu).

Xét các số nguyên ~x~ thỏa ~1 \le x \le K~. Gọi ~S(x)~ là tổng các chữ số trong biểu diễn thập phân của ~x~.

Yêu cầu

Hãy đếm số lượng số nguyên ~x~ trong đoạn ~[1, K]~ sao cho ~S(x)~ là bội của ~D~, tức là ~S(x) \equiv 0 \pmod D~.

In kết quả theo modulo ~10^9+7~.

Dữ liệu

• Dòng 1: xâu ~K~ (biểu diễn thập phân của ~K~)
• Dòng 2: số nguyên ~D~

Kết quả

• In ra số lượng số nguyên thỏa mãn, lấy modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

30
4

Output

6

Ví dụ 2

Input

1000000009
1

Output

2

Ví dụ 3

Input

98765432109876543210
58

Output

635270834

Giải thích

Ví dụ 1

Có ~6~ số thỏa: ~4, 8, 13, 17, 22, 26~ (tổng chữ số chia hết cho ~4~).

Ví dụ 2

Vì ~D=1~ nên mọi số đều thỏa, do đó đáp án là ~K \bmod (10^9+7)~.

Ví dụ 3

Ví dụ minh hoạ trường hợp ~K~ rất lớn.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le K < 10^{10000}~
• ~1 \le D \le 100~

Cho số nguyên dương ~N~ và một xâu ~s~ độ dài ~N-1~ chỉ gồm các ký tự < và >.

Hãy xét các hoán vị ~p=(p_1,p_2,\ldots,p_N)~ của dãy ~1,2,\ldots,N~. Hoán vị ~p~ được gọi là hợp lệ nếu với mọi ~i~ ~(1 \le i \le N-1)~:

• Nếu ~s_i = '<'~ thì ~p_i < p_{i+1}~.
• Nếu ~s_i = '>'~ thì ~p_i > p_{i+1}~.

Yêu cầu

Đếm số hoán vị hợp lệ. In kết quả theo modulo ~10^9+7~.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• Dòng 2: xâu ~s~ độ dài ~N-1~ gồm < và >.

Kết quả

• In ra số hoán vị hợp lệ, lấy modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

4
<><

Output

5

Ví dụ 2

Input

5
<<<<

Output

1

Ví dụ 3

Input

20

> > > > <>>><>><>>><<>>

Output

217136290

Giải thích

Ví dụ 1

Có đúng ~5~ hoán vị thỏa các dấu bất đẳng thức.

Ví dụ 2

Chỉ có hoán vị tăng dần ~(1,2,3,4,5)~ thỏa ~<<<<~.

Ví dụ 3

Ví dụ minh họa với ~N~ lớn, kết quả cần lấy modulo.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le N \le 3000~
• ~|s| = N-1~, ~s~ chỉ gồm < và >.

Có ~N~ bạn được đánh số từ ~1~ đến ~N~.

Với mọi cặp ~i, j~ ~(1 \le i, j \le N)~, mức độ hợp nhóm giữa bạn ~i~ và ~j~ được cho bởi số nguyên ~a_{i,j}~. Biết rằng:

• ~a_{i,i}=0~
• ~a_{i,j}=a_{j,i}~

Bạn cần chia ~N~ bạn thành một số nhóm bất kỳ, sao cho mỗi bạn thuộc đúng một nhóm.

Sau khi chia nhóm, với mỗi cặp ~i<j~, nếu ~i~ và ~j~ nằm <strong>cùng một nhóm thì tổng điểm tăng thêm ~a_{i,j}~.

Yêu cầu

Tìm tổng điểm lớn nhất có thể đạt được.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• ~N~ dòng tiếp theo: dòng thứ ~i~ gồm ~N~ số nguyên ~a_{i,1}, a_{i,2}, \ldots, a_{i,N}~.

Kết quả

• In ra một số nguyên: tổng điểm lớn nhất.

Ví dụ

Ví dụ 1

Input

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

Output

20

Ví dụ 2

Input

4
0 5 -10 -10
5 0 -10 -10
-10 -10 0 7
-10 -10 7 0

Output

12

Giải thích

Ví dụ 1

Chia nhóm tối ưu là {~1,3~} và {~2~}, được ~20~ điểm.

Ví dụ 2

Chia nhóm tối ưu là {~1,2~} (được ~5~ điểm) và {~3,4~} (được ~7~ điểm), tổng ~12~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 16~
• ~|a_{i,j}| \le 10^9~
• ~a_{i,i}=0~, ~a_{i,j}=a_{j,i}~

Bạn cần chọn một xâu nhị phân độ dài ~N~ (chỉ gồm các ký tự ~0~ và ~1~).

Điểm của xâu được tính theo ~M~ đoạn cho trước. Với mỗi ~i~ ~(1 \le i \le M)~, nếu trong đoạn ký tự từ vị trí ~l_i~ đến ~r_i~ (tính cả hai đầu) có xuất hiện ít nhất một ký tự ~1~, thì cộng thêm ~a_i~ điểm.

Yêu cầu

Tìm giá trị điểm lớn nhất có thể đạt được.

Dữ liệu

• Dòng 1: hai số nguyên ~N~, ~M~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên ~l_i~, ~r_i~, ~a_i~.

Kết quả

• In ra một số nguyên: điểm lớn nhất có thể đạt được.

Ví dụ

Ví dụ 1

Input

5 3
1 3 10
2 4 -10
3 5 10

Output

20

Ví dụ 2

Input

3 4
1 3 100
1 1 -10
2 2 -20
3 3 -30

Output

90

Giải thích

Ví dụ 1

Chọn xâu 10001.
Đoạn ~[1,3]~ và ~[3,5]~ đều có ít nhất một ~1~ nên được cộng ~10 + 10 = 20~; đoạn ~[2,4]~ không có ~1~ nên không bị cộng ~-10~. Kết quả là ~20~.

Ví dụ 2

Chọn xâu 100.
Đoạn ~[1,3]~ và ~[1,1]~ có ~1~ nên điểm là ~100 + (-10) = 90~.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~1 \le N \le 2 \cdot 10^5~
• ~1 \le M \le 2 \cdot 10^5~
• ~1 \le l_i \le r_i \le N~
• ~|a_i| \le 10^9~
• Đáp án có thể không vừa kiểu 32-bit.

Có ~N~ khối (block) được đánh số từ ~1~ đến ~N~. Khối thứ ~i~ có:

• khối lượng ~w_i~
• độ chịu lực ~s_i~
• giá trị ~v_i~

Bạn muốn xây một tháp bằng cách chọn một số khối và xếp chúng theo một thứ tự bất kỳ từ trên xuống dưới. Tháp phải thỏa điều kiện:

• Với mỗi khối ~i~ nằm trong tháp, tổng khối lượng của các khối nằm phía trên khối ~i~ không vượt quá ~s_i~.

Yêu cầu

Tìm tổng giá trị lớn nhất của các khối có thể đặt trong một tháp hợp lệ.

Dữ liệu

• Dòng 1: số nguyên ~N~.
• ~N~ dòng tiếp theo: dòng thứ ~i~ gồm ~w_i~, ~s_i~, ~v_i~.

Kết quả

• In ra một số nguyên: tổng giá trị lớn nhất.

Ví dụ

Ví dụ 1

Input

3
2 2 20
2 1 30
3 1 40

Output

50

Ví dụ 2

Input

4
1 2 10
3 1 10
2 4 10
1 6 10

Output

40

Giải thích

Ví dụ 1

Xếp từ trên xuống: khối ~2~ rồi khối ~1~.
Khối ~1~ chịu khối lượng phía trên là ~2 \le 2~, hợp lệ, tổng giá trị ~30+20=50~.

Ví dụ 2

Có thể xếp đủ cả 4 khối theo thứ tự từ trên xuống: ~1,2,3,4~, tổng giá trị ~40~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N \le 10^3~
• ~1 \le w_i, s_i \le 10^4~
• ~1 \le v_i \le 10^9~
• Đáp án có thể vượt 32-bit.

Có một lưới ô vuông gồm ~H~ hàng và ~W~ cột. Ô ở hàng ~i~ (từ trên xuống) và cột ~j~ (từ trái sang) được ký hiệu là ~(i, j)~.

Trong lưới có ~N~ ô là tường: ~(r_1,c_1), (r_2,c_2), \ldots, (r_N,c_N)~; các ô còn lại là ô trống. Bảo đảm ~(1,1)~ và ~(H,W)~ là ô trống.

Bạn xuất phát từ ô ~(1,1)~ và muốn đi đến ~(H,W)~ bằng cách lặp lại thao tác:

• đi sang phải 1 ô (từ ~(i,j)~ sang ~(i,j+1)~), hoặc
• đi xuống 1 ô (từ ~(i,j)~ sang ~(i+1,j)~),

và chỉ được đi qua các ô trống.

Yêu cầu

Hãy đếm số đường đi từ ~(1,1)~ đến ~(H,W)~, lấy modulo ~10^9+7~.

Dữ liệu

• Dòng 1: ~H~ ~W~ ~N~
• ~N~ dòng tiếp theo: dòng thứ ~i~ gồm ~r_i~ ~c_i~

Kết quả

• In ra số đường đi, modulo ~10^9+7~.

Ví dụ

Ví dụ 1

Input

3 4 2
2 2
1 4

Output

3

Ví dụ 2

Input

5 2 2
2 1
4 2

Output

0

Ví dụ 3

Input

5 5 4
3 1
3 5
1 3
5 3

Output

24

Ví dụ 4

Input

100000 100000 1
50000 50000

Output

123445622

Giải thích

Ví dụ 1

Có đúng ~3~ đường đi hợp lệ (tránh các ô tường).

Ví dụ 2

Mọi đường đi đều bị chặn nên không tồn tại đường đi nào.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le H, W \le 10^5~
• ~1 \le N \le 3000~
• ~1 \le r_i \le H~, ~1 \le c_i \le W~
• Các ô ~(r_i,c_i)~ đôi một khác nhau
• ~(1,1)~ và ~(H,W)~ là ô trống

Có ~N~ hòn đá được đánh số từ ~1~ đến ~N~. Độ cao của hòn đá thứ ~i~ là ~h_i~, và biết rằng ~h_1 < h_2 < \cdots < h_N~.

Ban đầu con ếch đứng ở hòn đá ~1~. Ếch sẽ thực hiện một số lần nhảy để đến được hòn đá ~N~ theo quy tắc:

• Nếu đang ở hòn đá ~i~, ếch có thể nhảy tới bất kỳ hòn đá ~j~ với ~i < j \le N~.
• Khi nhảy từ ~i~ sang ~j~, chi phí phát sinh là ~ (h_j - h_i)^2 + C ~.

Yêu cầu

Hãy tìm tổng chi phí nhỏ nhất để ếch đi từ hòn đá ~1~ đến hòn đá ~N~.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~C~.
• Dòng 2: ~N~ số nguyên ~h_1, h_2, \ldots, h_N~ (tăng строго).

Kết quả

• In ra một số nguyên: tổng chi phí nhỏ nhất.

Ví dụ

Ví dụ 1

Input

5 6
1 2 3 4 5

Output

20

Ví dụ 2

Input

2 1000000000000
500000 1000000

Output

1250000000000

Ví dụ 3

Input

8 5
1 3 4 5 10 11 12 13

Output

62

Giải thích

Ví dụ 1

Đi theo đường ~1 \to 3 \to 5~:

• Chi phí ~((3-1)^2 + 6) + ((5-3)^2 + 6) = 20~.

Ví dụ 2

Chỉ có một lần nhảy ~1 \to 2~, chi phí ~ (1000000-500000)^2 + 10^{12} = 1.25 \cdot 10^{12} ~.

Ví dụ 3

Một cách tối ưu là ~1 \to 2 \to 4 \to 5 \to 8~ (tổng chi phí bằng ~62~).

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le N \le 2 \cdot 10^5~
• ~1 \le C \le 10^{12}~
• ~1 \le h_1 < h_2 < \cdots < h_N \le 10^6~
• Đáp án có thể không vừa kiểu 32-bit.

Có một đồ thị có hướng ~G~ gồm ~N~ đỉnh và ~M~ cạnh. Các đỉnh được đánh số từ ~1~ đến ~N~. Với mỗi ~i~ ~(1 \le i \le M)~, cạnh có hướng thứ ~i~ đi từ đỉnh ~x_i~ tới đỉnh ~y_i~.

Biết rằng ~G~ không có chu trình có hướng (tức là ~G~ là DAG).

Yêu cầu

Hãy tìm độ dài của đường đi có hướng dài nhất trong ~G~.

Ở đây, độ dài của một đường đi có hướng được tính bằng số cạnh trên đường đi đó.

Dữ liệu

• Dòng 1: hai số nguyên ~N~ và ~M~.
• ~M~ dòng tiếp theo: dòng thứ ~i~ gồm hai số nguyên ~x_i~ ~y_i~ mô tả cạnh ~x_i \to y_i~.

Kết quả

• In ra một số nguyên: độ dài đường đi có hướng dài nhất.

Ví dụ

Ví dụ 1

Input

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

Output

3

Ví dụ 2

Input

6 3
2 3
4 5
5 6

Output

2

Ví dụ 3

Input

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

Output

3

Giải thích

Ví dụ 1

Một đường đi dài nhất là ~1 \to 3 \to 2 \to 4~, có ~3~ cạnh.

Ví dụ 2

Đường đi dài nhất là ~4 \to 5 \to 6~, có ~2~ cạnh.

Ràng buộc và chấm điểm

Ràng buộc

• Mọi giá trị trong input đều là số nguyên.
• ~2 \le N \le 10^5~
• ~1 \le M \le 10^5~
• ~1 \le x_i, y_i \le N~
• Các cặp ~(x_i, y_i)~ đôi một khác nhau.
• ~G~ không có chu trình có hướng.