| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2013 - Partitioning the Farm | 100 (p) | 4.0s | 512M |
| 2 | USACO 2013 - Taxi | 100 (p) | 4.0s | 512M |
| 3 | USACO 2013 - Route Design | 100 (p) | 4.0s | 512M |
Trang trại của Farmer John được chia thành một lưới vuông gồm \(N \times N\) đồng cỏ (\(2 \le N \le 15\)). Hiện tại, có một hàng rào bao quanh bên ngoài trang trại, nhưng bò có thể tự do di chuyển từ đồng cỏ này sang đồng cỏ khác.
Farmer John đã quyết định xây hàng rào để ngăn cách những con bò với nhau. Do các quy định về quy hoạch, mỗi hàng rào phải là một đường ngang hoặc dọc chạy xuyên suốt toàn bộ trang trại và không được đi qua bất kỳ đồng cỏ nào. Farmer John chỉ có đủ tiền để xây nhiều nhất \(K\) hàng rào (\(1 \le K \le 2N - 2\)).
Farmer John muốn xây các hàng rào sao cho số bò trong nhóm lớn nhất được tạo thành là nhỏ nhất (hai con bò thuộc cùng một nhóm nếu chúng có thể đi tới nhau mà không phải đi xuyên qua bất kỳ hàng rào nào). Biết số bò hiện có trong mỗi đồng cỏ, hãy giúp Farmer John tính số bò trong nhóm lớn nhất nếu ông xây hàng rào một cách tối ưu.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\).
\(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số mô tả số bò trong từng đồng cỏ của một hàng trên trang trại. Mỗi đồng cỏ có ít nhất 0 và nhiều nhất 1000 con bò.
In ra số bò nhỏ nhất có thể của nhóm lớn nhất.
Ví dụ 1
3 2
1 1 2
1 1 2
2 2 44Farmer John nên xây hàng rào giữa cột 2 và cột 3, đồng thời giữa hàng 2 và hàng 3. Cách này tạo ra 4 nhóm, mỗi nhóm có 4 con bò.
USACO 2013 February Contest, Gold — Problem 1: Partitioning the Farm
Tác giả đề: Brian Dean, 2013.
Bessie đang điều hành một dịch vụ taxi cho những con bò khác trong trang trại. Những con bò đang tụ tập tại nhiều vị trí khác nhau dọc theo một hàng rào dài \(M\) (\(1 \le M \le 1\,000\,000\,000\)). Thật không may, chúng đã chán những vị trí hiện tại và mỗi con đều muốn đi tới một nơi khác dọc theo hàng rào. Bessie phải đón từng người bạn tại vị trí xuất phát rồi chở họ tới điểm đến. Xe của Bessie khá nhỏ nên mỗi lần cô chỉ có thể chở một con bò. Bò có thể lên và xuống xe tức thì.
Để tiết kiệm xăng, Bessie muốn giảm thiểu tổng quãng đường cô phải lái xe. Biết vị trí xuất phát và vị trí đích của mỗi con trong số \(N\) con bò (\(1 \le N \le 100\,000\)), hãy xác định quãng đường ít nhất Bessie phải lái. Bessie nhận ra rằng để tiết kiệm xăng nhiều nhất, đôi khi cô có thể cần cho một con bò xuống tại một vị trí không phải điểm đến của nó.
Bessie bắt đầu ở điểm ngoài cùng bên trái của hàng rào, vị trí 0, và phải kết thúc hành trình tại điểm ngoài cùng bên phải của hàng rào, vị trí \(M\).
Dòng đầu tiên chứa \(N\) và \(M\), cách nhau bởi một dấu cách.
Dòng thứ \(i+1\) trong \(N\) dòng tiếp theo chứa hai số nguyên \(s_i\) và \(t_i\) cách nhau bởi một dấu cách (\(0 \le s_i, t_i \le M\)), lần lượt cho biết vị trí xuất phát và vị trí đích của con bò thứ \(i\).
In ra một số nguyên duy nhất cho biết tổng quãng đường Bessie phải lái. Lưu ý rằng kết quả có thể không vừa trong một số nguyên 32 bit.
Ví dụ 1
2 10
0 9
6 512Có hai con bò đang chờ được chở dọc theo một hàng rào dài 10. Con bò thứ nhất muốn đi từ vị trí 0 (nơi Bessie bắt đầu) tới vị trí 9. Con bò thứ hai muốn đi từ vị trí 6 tới vị trí 5.
Bessie đón con bò thứ nhất tại vị trí 0 và lái tới vị trí 6. Tại đó, cô cho con bò thứ nhất xuống, chở con bò thứ hai tới điểm đến của nó rồi quay lại đón con bò thứ nhất. Cô đưa con bò thứ nhất xuống tại điểm đến rồi lái nốt quãng đường còn lại tới phía bên phải của hàng rào.
USACO 2013 February Contest, Gold — Problem 2: Taxi
Tác giả đề: Mark Gordon và Richard Peng, 2013.
Sau khi thoát khỏi trang trại, Bessie quyết định mở một công ty du lịch dọc theo sông Amoozon. Có một số địa điểm du lịch nằm ở hai bên bờ sông, mỗi địa điểm có một giá trị nguyên biểu thị mức độ thú vị của nó.
Các địa điểm du lịch được nối với nhau bởi những tuyến đường băng qua sông (nghĩa là không có tuyến đường nào nối hai địa điểm ở cùng một bên bờ). Bessie muốn thiết kế một chuyến tham quan cho khách hàng và cần bạn giúp đỡ. Một chuyến tham quan là một dãy các địa điểm du lịch sao cho hai địa điểm kề nhau được nối bởi một tuyến đường. Để phục vụ khách hàng tốt nhất, cô muốn tìm chuyến tham quan làm tối đa tổng giá trị của tất cả các địa điểm được ghé thăm.
Tuy nhiên, Bessie có thể tổ chức nhiều chuyến tham quan như vậy cùng lúc. Vì thế, điều quan trọng là không có hai tuyến đường nào trong một chuyến tham quan giao nhau. Hai tuyến đường \((a \leftrightarrow x)\) và \((b \leftrightarrow y)\) giao nhau khi và chỉ khi một trong các điều kiện sau đúng: \(a < b\) và \(y < x\); \(b < a\) và \(x < y\); hoặc \(a = b\) và \(x = y\).
Hãy giúp Bessie tìm chuyến tham quan tốt nhất cho công ty của cô. Bessie có thể bắt đầu và kết thúc tại bất kỳ địa điểm nào ở bất kỳ bên bờ nào của sông Amoozon.
Dòng đầu tiên chứa ba số nguyên \(N\) (\(1 \le N \le 40\,000\)), \(M\) (\(1 \le M \le 40\,000\)) và \(R\) (\(0 \le R \le 100\,000\)), cách nhau bởi dấu cách, lần lượt biểu thị số địa điểm ở bờ trái, số địa điểm ở bờ phải và số tuyến đường.
\(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa một số nguyên \(L_i\) (\(0 \le L_i \le 40\,000\)), biểu thị giá trị của địa điểm du lịch thứ \(i\) ở bờ trái.
\(M\) dòng tiếp theo: dòng thứ \(i+N+1\) chứa một số nguyên \(R_i\) (\(0 \le R_i \le 40\,000\)), biểu thị giá trị của địa điểm du lịch thứ \(i\) ở bờ phải.
\(R\) dòng tiếp theo: mỗi dòng chứa hai số nguyên \(I\) (\(1 \le I \le N\)) và \(J\) (\(1 \le J \le M\)), cách nhau bởi một dấu cách, cho biết có một tuyến đường hai chiều giữa địa điểm \(I\) ở bờ trái và địa điểm \(J\) ở bờ phải.
In ra một số nguyên duy nhất cho biết tổng giá trị lớn nhất có thể đạt được trong một chuyến tham quan.
Ví dụ 1
3 2 4
1
1
5
2
2
1 1
2 1
3 1
2 28Có ba địa điểm ở bờ trái sông Amoozon với các giá trị 1, 1 và 5. Có hai địa điểm ở bờ phải với các giá trị 2 và 2. Có bốn tuyến đường nối các địa điểm ở hai bên bờ sông.
Chuyến tham quan tối ưu đi từ địa điểm 1 ở bờ trái, tới địa điểm 1 ở bờ phải và kết thúc tại địa điểm 3 ở bờ trái. Các địa điểm này lần lượt có giá trị 1, 2 và 5, nên tổng giá trị của chuyến đi là 8.
USACO 2013 February Contest, Gold — Problem 3: Route Design
Tác giả đề: Yan Gu, 2013.