USACO 2013 - Tháng 2 - Hạng Bạc

Farmer John đã xếp \(N\) kiện cỏ khô (\(1 \le N \le 50\,000\)) ở giữa một cánh đồng. Nếu coi cánh đồng là một lưới \(1\,000\,000 \times 1\,000\,000\) gồm các ô vuông \(1 \times 1\), thì mỗi kiện cỏ khô chiếm đúng một ô (dĩ nhiên, không có hai kiện cỏ khô nào chiếm cùng một ô).

FJ nhận thấy tất cả các kiện cỏ khô tạo thành một vùng liên thông lớn, nghĩa là từ bất kỳ kiện cỏ nào, ta có thể đến bất kỳ kiện cỏ nào khác bằng một chuỗi bước đi về phía bắc, nam, đông hoặc tây sang các kiện cỏ kề cạnh trực tiếp. Tuy nhiên, vùng liên thông gồm các kiện cỏ có thể chứa những "lỗ hổng" — các vùng trống bị kiện cỏ bao quanh hoàn toàn.

Hãy giúp FJ xác định chu vi của vùng được tạo bởi các kiện cỏ khô. Lưu ý rằng các lỗ hổng không đóng góp vào chu vi.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng kiện cỏ khô \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa vị trí \((x,y)\) của một kiện cỏ khô, trong đó \(x\) và \(y\) đều là số nguyên trong khoảng từ \(1\) đến \(1\,000\,000\). Vị trí \((1,1)\) là ô dưới cùng bên trái trong cánh đồng của FJ, còn vị trí \((1000000,1000000)\) là ô trên cùng bên phải.

Dữ liệu ra

In ra chu vi của vùng liên thông gồm các kiện cỏ khô.

Ví dụ

8
10005 200003
10005 200004
10008 200004
10005 200005
10006 200003
10007 200003
10007 200004
10006 200005

14

XX 
X XX
XXX

Nguồn

USACO 2013 February Contest, Silver — Problem 1: Perimeter

Tác giả đề: Brian Dean, 2013.

Một trong những cánh đồng của Farmer John đặc biệt gồ ghề, và ông muốn mua một chiếc máy kéo mới để lái trên đó. Cánh đồng được mô tả bởi một lưới \(N \times N\) gồm các độ cao nguyên không âm (\(1 \le N \le 500\)). Một chiếc máy kéo có khả năng di chuyển từ một ô sang ô kề cạnh (một bước về phía bắc, đông, nam hoặc tây) có độ chênh cao \(D\) có giá chính xác \(D\) đơn vị tiền.

FJ muốn trả đủ tiền cho chiếc máy kéo để khi bắt đầu từ một ô nào đó trên cánh đồng, ông có thể lái máy kéo đi thăm ít nhất một nửa số ô của cánh đồng (nếu tổng số ô là số lẻ, ông muốn thăm ít nhất một nửa số ô được làm tròn lên). Hãy giúp ông tính chi phí tối thiểu cần thiết để mua một chiếc máy kéo có thể thực hiện nhiệm vụ này.

Dữ liệu vào

• Dòng đầu tiên chứa giá trị \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên không âm cách nhau bởi dấu cách (mỗi số không vượt quá \(1\) triệu), mô tả một hàng của cánh đồng FJ.

Dữ liệu ra

In ra chi phí tối thiểu của một chiếc máy kéo có khả năng di chuyển trên ít nhất một nửa cánh đồng của FJ.

Ví dụ

5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 3

3

Nguồn

USACO 2013 February Contest, Silver — Problem 2: Tractor

Tác giả đề: Kalki Seksaria và Brian Dean, 2013.

\(N\) con bò của Farmer John (\(1 \le N \le 10\,000\)) được đánh số thuận tiện từ \(1\) đến \(N\). Việc vắt sữa bò thứ \(i\) mất \(T(i)\) đơn vị thời gian. Thật không may, do cách bố trí chuồng của FJ, một số con bò phải được vắt sữa trước những con khác. Nếu bò \(A\) phải được vắt sữa trước bò \(B\), thì FJ cần hoàn tất việc vắt sữa bò \(A\) trước khi có thể bắt đầu vắt sữa bò \(B\).

Để vắt sữa đàn bò nhanh nhất có thể, FJ đã thuê rất nhiều người làm nông hỗ trợ công việc — đủ người để vắt sữa đồng thời bao nhiêu con bò cũng được. Tuy nhiên, dù các con bò có thể được vắt sữa cùng lúc, các ràng buộc yêu cầu một số con bò phải được vắt sữa trước những con khác vẫn giới hạn tốc độ hoàn thành toàn bộ quá trình. Hãy giúp FJ tính tổng thời gian tối thiểu mà quá trình vắt sữa phải mất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) (số lượng bò) và \(M\) (số lượng ràng buộc về thứ tự vắt sữa; \(1 \le M \le 50\,000\)), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo: dòng thứ \(i\) chứa giá trị \(T(i)\) (\(1 \le T(i) \le 100\,000\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\), cách nhau bởi dấu cách, cho biết bò \(A\) phải được vắt sữa xong hoàn toàn trước khi có thể bắt đầu vắt sữa bò \(B\). Các ràng buộc này không bao giờ tạo thành chu trình, vì vậy luôn tồn tại lời giải.

Dữ liệu ra

In ra lượng thời gian tối thiểu cần để vắt sữa tất cả các con bò.

Ví dụ

3 1
10
5
6
3 2

11

Nguồn

USACO 2013 February Contest, Silver — Problem 3: Milk Scheduling

Tác giả đề: Kalki Seksaria, 2013.