| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2014 - Watering the Fields | 100 (p) | 4.0s | 512M |
| 2 | USACO 2014 - The Lazy Cow | 100 (p) | 4.0s | 512M |
| 3 | USACO 2014 - Mooo Moo | 100 (p) | 4.0s | 512M |
Do thiếu mưa, Farmer John muốn xây dựng một hệ thống tưới tiêu để dẫn nước giữa \(N\) cánh đồng của mình (\(1 \le N \le 2\,000\)).
Mỗi cánh đồng \(i\) được mô tả bởi một điểm \((x_i,y_i)\) riêng biệt trên mặt phẳng hai chiều, với \(0 \le x_i,y_i \le 1\,000\). Chi phí xây dựng một đường ống dẫn nước giữa hai cánh đồng \(i\) và \(j\) bằng bình phương khoảng cách Euclid giữa chúng:
FJ muốn xây dựng một hệ thống đường ống có chi phí nhỏ nhất sao cho tất cả các cánh đồng đều được nối với nhau, tức là nước ở một cánh đồng bất kỳ có thể đi theo một dãy đường ống để đến bất kỳ cánh đồng nào khác.
Đáng tiếc, nhà thầu đang giúp FJ lắp đặt hệ thống tưới tiêu từ chối lắp bất kỳ đường ống nào có chi phí (bình phương độ dài Euclid) nhỏ hơn \(C\) (\(1 \le C \le 1\,000\,000\)).
Hãy giúp FJ tính số tiền nhỏ nhất cần trả để nối tất cả các cánh đồng bằng một mạng lưới đường ống.
In ra chi phí nhỏ nhất của một mạng lưới đường ống nối tất cả các cánh đồng, hoặc \(-1\) nếu không thể xây dựng mạng lưới như vậy.
Ví dụ 1
3 11
0 2
5 0
4 346Có \(3\) cánh đồng tại các vị trí \((0,2)\), \((5,0)\) và \((4,3)\). Nhà thầu chỉ lắp những đường ống có chi phí ít nhất là \(11\).
FJ không thể xây đường ống giữa hai cánh đồng tại \((4,3)\) và \((5,0)\) vì chi phí chỉ là \(10\). Do đó, ông xây một đường ống giữa \((0,2)\) và \((5,0)\) với chi phí \(29\), cùng một đường ống giữa \((0,2)\) và \((4,3)\) với chi phí \(17\).
USACO 2014 March Contest, Silver — Watering the Fields
Tác giả: Brian Dean, 2014.
Đó là một ngày hè nóng nực và cô bò Bessie cảm thấy khá lười biếng. Cô muốn chọn một vị trí trong cánh đồng để có thể tiếp cận nhiều cỏ ngon nhất có thể mà chỉ phải đi một quãng ngắn.
Cánh đồng nơi Bessie sống được mô tả bởi một lưới gồm \(N \times N\) ô vuông (\(1 \le N \le 400\)). Ô ở hàng \(r\), cột \(c\) (\(1 \le r,c \le N\)) chứa \(G(r,c)\) đơn vị cỏ (\(0 \le G(r,c) \le 1\,000\)). Từ ô xuất phát trên lưới, Bessie chỉ sẵn lòng đi nhiều nhất \(K\) bước (\(0 \le K \le 2N\)). Mỗi bước đưa cô đến ô nằm ngay phía bắc, nam, đông hoặc tây của vị trí hiện tại.
Ví dụ, giả sử lưới như sau, trong đó (B) biểu thị vị trí ban đầu của Bessie (ở đây là hàng \(3\), cột \(3\)):
50 5 25* 6 17
14 3* 2* 7* 21
99* 10* 1*(B) 2* 80*
8 7* 5* 23* 11
10 0 78* 1 9
Nếu \(K=2\), Bessie chỉ có thể đến các vị trí được đánh dấu *.
Hãy giúp Bessie xác định lượng cỏ lớn nhất mà cô có thể tiếp cận nếu chọn vị trí ban đầu tối ưu trên lưới.
In ra lượng cỏ lớn nhất Bessie có thể tiếp cận nếu chọn vị trí ban đầu tối ưu, tức là vị trí cho phép cô tiếp cận nhiều cỏ nhất.
Ví dụ 1
5 2
50 5 25 6 17
14 3 2 7 21
99 10 1 2 80
8 7 5 23 11
10 0 78 1 9342Trong ví dụ trên, Bessie có thể tiếp cận tổng cộng \(342\) đơn vị cỏ nếu đứng ở chính giữa lưới.
USACO 2014 March Contest, Silver — The Lazy Cow
Tác giả: Brian Dean, 2014.
Farmer John đã hoàn toàn quên mất mình sở hữu bao nhiêu con bò! Ông quá xấu hổ để ra đồng đếm vì không muốn những cô bò nhận ra sự đãng trí của mình. Thay vào đó, ông quyết định bí mật đếm bò bằng cách đặt micrô tại những cánh đồng nơi chúng thường tụ tập, với suy luận rằng có thể xác định số bò từ tổng âm lượng của tất cả tiếng rống nghe được.
\(N\) cánh đồng của FJ (\(1 \le N \le 100\)) nằm thành một hàng dọc theo một con đường thẳng dài. Mỗi cánh đồng có thể chứa nhiều giống bò; FJ sở hữu bò thuộc \(B\) giống khác nhau (\(1 \le B \le 20\)), và một cô bò giống \(i\) rống với âm lượng \(V(i)\) (\(1 \le V(i) \le 100\)). Hơn nữa, một luồng gió mạnh thổi dọc con đường, mang âm thanh theo một hướng từ trái sang phải: nếu âm lượng tiếng rống trong một cánh đồng là \(X\), âm thanh này sẽ đóng góp \(X-1\) vào tổng âm lượng tiếng rống ở cánh đồng kế tiếp (rồi \(X-2\) ở cánh đồng sau nữa, v.v.). Nói cách khác, âm lượng tiếng rống tại một cánh đồng bằng tổng đóng góp của những cô bò trong chính cánh đồng đó cộng với \(X-1\), trong đó \(X\) là tổng âm lượng tiếng rống tại cánh đồng ngay trước.
Cho âm lượng tiếng rống mà FJ ghi lại tại mỗi cánh đồng, hãy tính số bò ít nhất mà FJ có thể sở hữu.
Âm lượng FJ ghi lại tại bất kỳ cánh đồng nào cũng không vượt quá \(100\,000\).
In ra số bò ít nhất mà FJ sở hữu, hoặc \(-1\) nếu không tồn tại cách bố trí bò nào phù hợp với dữ liệu vào.
Ví dụ 1
5 2
5
7
0
17
16
20
194FJ có \(5\) cánh đồng với âm lượng tiếng rống lần lượt là \(0,17,16,20,19\). Có hai giống bò: giống thứ nhất rống với âm lượng \(5\), giống còn lại rống với âm lượng \(7\).
Tại cánh đồng \(2\) có \(2\) cô bò giống số \(1\) và \(1\) cô bò giống số \(2\); tại cánh đồng \(4\) còn có thêm một cô bò giống số \(1\).
USACO 2014 March Contest, Silver — Mooo Moo
Tác giả: Brian Dean, 2014.