Hãy đếm xem có bao nhiêu mảng khác nhau \(a_1,a_2,...,a_n\) trong đó \(a_i\) nhận các giá trị nguyên dương trong đoạn \([1,M]\) sao cho tồn tại ít nhất một đoạn \(K\) giá trị liên tiếp giống nhau?.

Ở đây hai mảng được gọi là khác nhau nếu như tồn tại ít nhất một vị trí mà giá trị phần tử hai mảng ở vị trí này là khác nhau.

Input

• Một dòng duy nhất chứa ba số nguyên dương lần lượt là \(n, M, K\).

Output

• Ghi ra một số nguyên duy nhất là số lượng mảng khác nhau tìm được. Con số này có thể rất lớn nên bạn chỉ cần lấy phần dư của nó khi chia cho \(10^9+7\).

Constants

• \(1\leq n,M,K\leq10^6\).

3 2 2 

6

Một nhà Toán học đang làm việc với các số nguyên tố cần sự giúp đỡ của bạn. Cụ thể, nhà
Toán học có \(T\) câu hỏi, mỗi câu hỏi là một cặp số \(L\) và \(R\), bạn cần trả lời số lượng số nguyên tố nằm
trong đoạn \([L, R]\), tính cả hai đầu. Nhận thấy các thí sinh tham gia Kỳ thi Olympic Truyền thống
30-4 có khả năng trả lời được câu hỏi này, nhà Toán học nhờ các bạn trợ giúp. Các bạn hãy giúp nhà
Toán học nhé.

Yêu cầu: Hãy viết chương trình trả lời các truy vấn của nhà Toán học.

Input

• Dòng đầu chứa số nguyên dương \(T\) (\(1 \le T \le 1000\)) là số truy vấn.
• \(T\) dòng tiếp theo, mỗi dòng ghi hai số nguyên dương, dòng thứ \(i+1\) ghi cặp số \(L_i, R_i\),
  (\(1 \le L_i \le R_i \le 10^9\)) là các tham số của truy vấn thứ \(i\).
• Tổng độ dài của các đoạn truy vấn không vượt quá \(10^6\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) chứa một số nguyên là
  câu trả lời của truy vấn thứ \(i\).

Scoring

• 50% số điểm của bài tương ứng với các test có \(L_i, R_i \le 10^5\) và tổng độ dài các đoạn truy
  vấn không vượt quá \(10^5\)

Example

2
1 50
10000000 10000050

15
1

Hai anh em An và Bình tham gia một trò chơi thám hiểm trên bảng số \(xTremeMaze\).
Bảng có kích thước \(N\)x\(M\) (\(N\) dòng và \(M\) cột). Các ô trong bảng được đánh số từ trái sang phải và từ
trên xuống dưới.

Tại mỗi ô của bảng có ghi một số nguyên là số điểm kinh nghiệm mà người chơi sẽ nhận được khi
đi vào ô này. Cần lưu ý là số điểm tại một số ô có thể là số âm; khi đó, điểm kinh nghiệm của người
chơi sẽ bị giảm nếu đi vào ô này.

An và Bình bắt đầu tại ô trái trên, đánh số là (\(1, 1\)). Mỗi lượt, một người chỉ có thể di chuyển tới ô
kề cạnh ngay phía dưới hoặc ô kề cạnh ngay bên phải và không được phép đi ra khỏi bảng. Khi đi
qua mỗi ô, người chơi nhận được số điểm kinh nghiệm bằng số nguyên ghi ở ô đó. Hành trình kết
thúc tại ô (\(N, M\)).

Mục tiêu của trò chơi này là hai anh em đạt được tổng số điểm cao nhất có thể. Theo quy định, các ô
mà An và Bình đi qua không được phép trùng nhau, ngoại trừ ô bắt đầu tại vị trí (\(1, 1\)) và ô kết thúc
tại vị trí (\(N, M\)). Quy ước: giá trị điểm kinh nghiệm tại ô (\(1, 1\)) và ô (\(N, M\)) đều bằng 0.

Yêu cầu: Hãy viết chương trình tính tổng số điểm kinh nghiệm lớn nhất mà An cùng với Bình đạt
được.

Input

• Dòng đầu chứa hai số nguyên \(N\) và M (\(2 \le N, M \le 200\)), số dòng và số cột của bảng.
• \(N\) dòng tiếp theo, mỗi dòng ghi M số nguyên là số điểm kinh nghiệm tại mỗi ô trên bảng.
  Điểm kinh nghiệm tại mỗi ô có giá trị tuyệt đối không vượt quá 100.

Output

• Ghi ra duy nhất một số nguyên là tổng điểm lớn nhất mà
  An cùng với Bình đạt được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \le 3\) và \(M \le 200\).
• Subtask \(2\) (\(40\%\) số điểm): \(N \le 50\) và \(M \le 50\).
• Subtask \(3\) (\(30\%\) số điểm): Không có điều kiện gì thêm.

Example

3 3
0 2 3
4 5 6
7 8 0

32

Hành tinh Marvelous Land gồm \(N\) thành phố, được kết nối với nhau bởi \(M\) tuyến đường hai chiều. Giữa hai thành phố chỉ có tối đa một tuyến đường nối chúng và không có tuyến đường nào nối một thành phố tới chính nó. Các thành phố được đánh số từ 1 tới \(N\). Trong đó có 2 thành phố là trung tâm kinh tế quan trọng là thành phố 1 và thành phố \(N\). Tuyến đường thứ \(i\) cho phép đi lại giữa hai thành phố \(u_i\) và \(v_i\) với \(t_i\) đơn vị thời gian. Một ngày nọ, người dân Marvelous Land khảo sát các con đường và nhận thấy cần nâng cấp mạng lưới đường hiện có, hoặc xây thêm một số tuyến đường hai chiều. Điều cần quan tâm nhất là tổng thời gian ngắn nhất để đi lại giữa 2 thành phố trung tâm kinh tế. Trước khi quyết định nâng cấp mạng lưới đường đi, cần xác định các tuyến đường trọng yếu là những tuyến đường mà không thể không đi qua khi muốn đi từ thành phố 1 tới thành phố \(N\) với tổng thời gian ngắn nhất.

Yêu cầu: Hãy viết chương trình đếm số lượng tuyến đường trọng yếu.

Input

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 10^5, 1 \le M \le 2 × 10^5\)), số thành phố và số
  tuyến đường.
• \(M\) dòng tiếp theo, mỗi dòng ghi ba số nguyên, dòng thứ \(i+1\) ghi số \(u_i, v_i, t_i\) (\(1 \le u_i, v_i \le N, 1 \le t_i \le 10^6\)) là các thông tin của tuyến đường thứ \(i\).

Output

• Ghi ra duy nhất một số nguyên là số tuyến đường trọng
  yếu.

Scoring

• 50% số điểm của bài tương ứng với các test có \(N \le 1000\) và \(M \le 1000\)

Example

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

3

Công ty bánh kẹo ABC chuẩn bị xây dựng hệ thống đại lý để giao bánh kẹo đến tất
cả địa điểm trong thành phố. Hàng ngày, từ mỗi đại lý các nhân viên dùng \(K\) loại xe với
trọng lượng lần lượt là \(P_1, P_2,…,P_K\) chuyên chở bánh kẹo đến các địa điểm còn lại.
Thành phố có \(N\) địa điểm (đánh số từ 1 đến \(N\)) và \(M\) con đường hai chiều nối trực tiếp
giữa các địa điểm, trên mỗi con đường có ghi một số nguyên dương cho biết trọng lượng
tối đa của xe được phép di chuyển trên con đường này. Giữa 2 địa điểm bất kì có thể có
nhiều con đường nối trực tiếp.

Để có thể giao hàng đến N địa điểm, công ty tìm cách chọn một số địa điểm để đặt
đại lý. Chi phí mỗi cách chọn phụ thuộc vào số lượng địa điểm được chọn làm đại lý,
số địa điểm càng ít thì chi phí càng thấp.

Yêu cầu:

• Hãy cho biết cách chọn có chi phí thấp nhất sẽ có số lượng địa điểm đặt
  đại lý là bao nhiêu.

Input

• Dòng 1 gồm ba số nguyên dương \(N (1≤ N ≤1000), M (1≤ M ≤100000), K (1≤ K ≤ 20)\).
• Dòng 2 gồm \(K\) số nguyên dương \(P_1, P2_, …, P_K (1≤ P_i ≤500)\)
• \(M\) dòng tiếp theo, dòng thứ \(i\) gồm ba số nguyên dương \(A_i, B_i, T_i (1 ≤T_i ≤ 500)\),
  cho biết con đường nối giữa địa điểm \(A_i\) đến \(B_i\) chịu được trọng lượng tối đa là
  \(T_i\). Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Output

• Ghi ra một dòng với số nguyên duy
  nhất cho biết số lượng địa điểm ít nhất.

Example

Nguồn: Olympic 30/4 năm 2018.

Phú hộ qua đời để lại cho 4 người con một mảnh đất hình vuông có kích thước \(n × n\), trên đó có trồng một số cây gỗ quí. Theo di chúc, mảnh đất sẽ được chia thành 4 phần, mỗi phần là một hình chữ nhật. Để tiết kiệm chi phí chia đất nên chỉ có thể thực hiện cắt mảnh đất bởi một nhát cắt theo chiều ngang và một nhát cắt theo chiều dọc. Các con của phú hộ đều thích có nhiều cây gỗ quí vì vậy họ sẽ chọn phần đất có nhiều cây gỗ quí hơn. Thứ tự nhận đất sẽ từ lớn tới nhỏ, người em út sẽ nhận phần có ít cây gỗ quí nhất.

Yêu cầu:

• Hãy chỉ cách chia đất để chênh lệch giữa số cây gỗ quí của người anh cả và của người em út là ít nhất.

Input

• Dòng thứ nhất ghi số nguyên dương \(n (2 ≤ n ≤ 500)\)
• Tiếp theo là \(n\) dòng, mỗi dòng ghi \(n\) số, số 0 hoặc số 1. Số 0 thể hiện vị trí không có cây gỗ quí, số 1 thể hiện vị trí có cây gỗ quí.

Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Output

• Một dòng ghi một số nguyên là số lượng chênh lệch cây gỗ quí ít nhất trên phần đất của người anh cả và của người em út.

Constants

• Có 50% số test tương ứng 50% số điểm có \(2 ≤ n ≤ 150\)
• Có 50% số test tương ứng 50% số điểm có \(150 < n ≤ 500.\)

Example

Nguồn: Olympic 30/4 năm 2018.

Sân golf được biểu diễn bởi một lưới kích thước \(M \times N (1≤M, N≤500)\). Mỗi ô của
lưới có độ cao trong khoảng 0 đến 109 so với mực nước biển.

Tại một vài ô trong lưới này là các vị trí có đặt lỗ, tức là nơi vận động viên sẽ đánh
bóng rơi vào đó và bắt buộc sẽ đi đến đó để nhặt bóng.

Ban tổ chức của Olympics muốn đánh giá độ chênh lệch độ cao \(D\) của sân golf bằng
cách làm như sau:

Cho một nhân viên bắt đầu di chuyển từ một vị trí đặt lỗ bất kỳ đến một trong bốn ô
kề cạnh với ô đang đứng, có trị tuyệt đối chênh lệch độ cao không quá \(D\). Tại ô mới
này, anh ta lại di chuyển tiếp sang một trong bốn ô kề cạnh có trị tuyệt đối chênh lệch
độ cao không quá \(D\). Cứ thế tiếp tục cho đến khi có thể đến được tất cả các lỗ.

Yêu cầu:

• Hãy xác định độ chênh lệch độ cao \(D\) nhỏ nhất mà từ một lỗ bất kỳ có thể
  đến được tất cả các lỗ còn lại.

Input

• Dòng 1: chứa 2 số nguyên \(M, N\).
• \(M\) dòng tiếp theo: mỗi dòng chứa \(N\) số nguyên là độ cao của ô.
• \(M\) dòng tiếp theo: mỗi dòng chứa \(N\) giá trị là 0 hoặc 1, trong đó ô có giá trị 1
  cho biết tại vị trí đó có lỗ, ngược lại thì tại đó không có lỗ.

Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Kết quả

• Một dòng duy nhất ghi số nguyên dương \(D\) cần tìm.

Example

Nguồn: Olympic 30/4 năm 2018.

Bài 1: Chia kẹo (6 điểm)

Example

5 2

2

Bài 2: Quà tặng (7 điểm)

Example

6 18
6 3 10 2 4 9

15

Bài 3: Khu vườn (7 điểm)

Example

4 100 200 1
1 4
2 3
3 2
4 0

210