USACO 2012 - Tháng 3 - Hạng Bạc

Sau một ngày dài làm việc, Farmer John hoàn toàn quên mất rằng mình đã để máy kéo ở giữa cánh đồng. Đàn bò của ông, vốn lúc nào cũng nghịch ngợm, quyết định chơi khăm Farmer John: chúng đặt \(N\) kiện cỏ khô (\(1 \leq N \leq 50\,000\)) tại nhiều vị trí khác nhau trên cánh đồng, khiến Farmer John không thể dễ dàng đưa máy kéo ra ngoài nếu chưa dọn một số kiện cỏ.

Vị trí của máy kéo cũng như vị trí của \(N\) kiện cỏ đều là các điểm trên mặt phẳng hai chiều có tọa độ nguyên trong khoảng \(1 \ldots 1000\). Không có kiện cỏ nào nằm tại vị trí ban đầu của máy kéo. Khi lái máy kéo, Farmer John chỉ có thể di chuyển theo các hướng song song với các trục tọa độ (bắc, nam, đông và tây), và mỗi lần di chuyển phải đi một số nguyên đơn vị. Chẳng hạn, ông có thể đi 2 đơn vị về phía bắc, rồi 3 đơn vị về phía đông. Máy kéo không thể đi vào một điểm đang có kiện cỏ.

Hãy giúp Farmer John xác định số kiện cỏ ít nhất ông cần dọn để giải thoát máy kéo, tức là để ông có thể lái máy kéo tới gốc tọa độ của mặt phẳng hai chiều.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: \(N\) và tọa độ \((x,y)\) ban đầu của máy kéo.
• \(N\) dòng tiếp theo, mỗi dòng chứa tọa độ \((x,y)\) của một kiện cỏ.

Dữ liệu ra

In ra số kiện cỏ ít nhất Farmer John phải dọn để mở một đường cho máy kéo đi tới gốc tọa độ.

Ví dụ

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

1

Nguồn

USACO 2012 March Contest, Silver Division — Tractor. Tác giả đề: Brian Dean (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=124

Farmer John đang gặp khó khăn trong việc giúp cây cối phát triển và cần bạn hỗ trợ tưới nước cho chúng đúng cách. Bạn được cho vị trí của \(N\) giọt mưa (\(1 \leq N \leq 100\,000\)) trên mặt phẳng hai chiều, trong đó \(y\) biểu thị độ cao thẳng đứng của giọt mưa và \(x\) biểu thị vị trí của nó trên một trục số một chiều:

Mỗi giọt rơi thẳng xuống dưới (về phía trục \(x\)) với tốc độ 1 đơn vị mỗi giây. Bạn muốn đặt chậu hoa rộng \(W\) của Farmer John ở đâu đó dọc theo trục \(x\) sao cho chênh lệch thời gian giữa giọt mưa đầu tiên và giọt mưa cuối cùng rơi trúng chậu ít nhất là một giá trị \(D\) nào đó (để hoa trong chậu nhận được thật nhiều nước). Một giọt nước rơi đúng vào mép chậu vẫn được tính là rơi trúng chậu.

Cho giá trị \(D\) và vị trí của \(N\) giọt mưa, hãy tính giá trị nhỏ nhất có thể của \(W\).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách, \(N\) và \(D\) (\(1 \leq D \leq 1\,000\,000\)).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa tọa độ \((x,y)\) cách nhau bởi dấu cách của giọt mưa \(i\); mỗi giá trị nằm trong khoảng \(0 \ldots 1\,000\,000\).

Dữ liệu ra

In ra một số nguyên duy nhất là chiều rộng nhỏ nhất có thể của chậu hoa. In -1 nếu không thể làm một chậu đủ rộng để hứng mưa trong ít nhất \(D\) đơn vị thời gian.

Ví dụ

4 5
6 3
2 4
4 10
12 15

2

Nguồn

USACO 2012 March Contest, Silver Division — Flowerpot. Tác giả đề: Brian Dean (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=125

Farmer John đang xây dựng một khu vườn được tạo cảnh quan đẹp mắt và cần di chuyển một lượng lớn đất trong quá trình này.

Khu vườn gồm một dãy \(N\) luống hoa (\(1 \leq N \leq 100\,000\)), trong đó ban đầu luống hoa \(i\) chứa \(A_i\) đơn vị đất. Farmer John muốn tạo lại cảnh quan khu vườn sao cho mỗi luống hoa \(i\) chứa \(B_i\) đơn vị đất. Tất cả các giá trị \(A_i\) và \(B_i\) đều là số nguyên trong khoảng \(0 \ldots 10\).

Để tạo cảnh quan cho khu vườn, Farmer John có một số lựa chọn: ông có thể mua một đơn vị đất và đặt nó vào một luống hoa tùy chọn với chi phí \(X\) đơn vị tiền; ông có thể lấy một đơn vị đất ra khỏi một luống hoa tùy chọn rồi chuyển nó đi nơi khác với chi phí \(Y\) đơn vị tiền; hoặc ông có thể vận chuyển một đơn vị đất từ luống hoa \(i\) đến luống hoa \(j\) với chi phí bằng \(Z\) nhân với \(|i-j|\). Hãy tính tổng chi phí nhỏ nhất để Farmer John hoàn thành dự án tạo cảnh quan.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(X\), \(Y\) và \(Z\) (\(0 \leq X, Y \leq 10^8\); \(0 \leq Z \leq 1000\)). Dòng \(i+1\) chứa hai số nguyên \(A_i\) và \(B_i\).

Dữ liệu ra

In ra tổng chi phí nhỏ nhất mà FJ cần bỏ ra để tạo cảnh quan.

Ví dụ

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

210

Lưu ý rằng bài này đã từng xuất hiện trong một kỳ thi USACO trước đây ở bảng Silver; tuy nhiên, các giới hạn trong phiên bản hiện tại đã được tăng lên đáng kể, vì vậy không nên kỳ vọng lời giải cho phiên bản trước, dễ hơn sẽ đạt được nhiều điểm.

Nguồn

USACO 2016 US Open Contest, Platinum - Landscaping: https://usaco.org/index.php?page=viewproblem2&cpid=650

Tác giả: Brian Dean.