Olympic Truyền thống 30/4 2018 - Tin học - Khối 10

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.