| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2015 - Piggyback | 100 (p) | 4.0s | 512M |
| 2 | USACO 2015 - Marathon | 100 (p) | 4.0s | 512M |
| 3 | USACO 2015 - Cow Jog | 100 (p) | 4.0s | 512M |
Bessie và cô em Elsie gặm cỏ ở những cánh đồng khác nhau vào ban ngày, còn buổi tối cả hai đều muốn đi bộ về chuồng để nghỉ ngơi. Là những cô bò thông minh, họ nghĩ ra một kế hoạch nhằm giảm thiểu tổng năng lượng cả hai tiêu hao khi di chuyển.
Bessie tiêu hao \(B\) đơn vị năng lượng khi đi từ một cánh đồng sang một cánh đồng kề bên, còn Elsie tiêu hao \(E\) đơn vị năng lượng khi đi sang một cánh đồng kề bên. Tuy nhiên, nếu Bessie và Elsie ở cùng một cánh đồng, Bessie có thể cõng Elsie trên vai và cả hai cùng di chuyển sang một cánh đồng kề bên mà chỉ tiêu hao \(P\) đơn vị năng lượng (trong đó \(P\) có thể nhỏ hơn đáng kể so với \(B+E\), lượng năng lượng Bessie và Elsie sẽ tiêu hao nếu tự đi riêng sang cánh đồng kề bên). Nếu \(P\) rất nhỏ, phương án tiết kiệm năng lượng nhất có thể là Bessie và Elsie đi đến một cánh đồng chung để gặp nhau, rồi cùng di chuyển theo kiểu cõng nhau trong phần còn lại của hành trình đến chuồng. Tất nhiên, nếu \(P\) lớn, việc Bessie và Elsie đi riêng vẫn có thể hợp lý nhất. Nhân tiện, cả Bessie và Elsie đều không hài lòng với thuật ngữ “piggyback”, vì họ không hiểu tại sao những chú lợn trong trang trại lại đáng được ghi hết công lao cho hình thức di chuyển tuyệt vời này.
Cho \(B\), \(E\), \(P\) cùng với sơ đồ trang trại, hãy tính lượng năng lượng nhỏ nhất cần thiết để Bessie và Elsie đến được chuồng.
Dòng đầu tiên chứa các số nguyên dương \(B\), \(E\), \(P\), \(N\) và \(M\). Tất cả các số này đều không vượt quá \(40\,000\). \(B\), \(E\) và \(P\) có ý nghĩa như mô tả ở trên. \(N\) là số cánh đồng trong trang trại (được đánh số từ 1 đến \(N\), với \(N \ge 3\)), còn \(M\) là số đường nối giữa các cánh đồng. Bessie và Elsie lần lượt xuất phát ở cánh đồng 1 và 2. Chuồng nằm ở cánh đồng \(N\).
\(M\) dòng tiếp theo, mỗi dòng mô tả một đường nối giữa một cặp cánh đồng khác nhau bằng hai số nguyên là chỉ số của hai cánh đồng. Các đường nối đều đi được theo hai chiều. Luôn có thể đi từ cánh đồng 1 đến cánh đồng \(N\), cũng như từ cánh đồng 2 đến cánh đồng \(N\), qua một chuỗi các đường nối như vậy.
In ra một số nguyên duy nhất là tổng năng lượng nhỏ nhất mà Bessie và Elsie cần tiêu hao để đến chuồng.
Ví dụ 1
4 4 5 8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 822Trong ví dụ này, Bessie đi từ 1 đến 4, còn Elsie đi từ 2 đến 3 rồi đến 4. Sau đó, họ cùng đi từ 4 đến 7 rồi đến 8.
USACO 2014 December Contest, Silver — Piggyback. Tác giả đề: Brian Dean, 2014.
Không hài lòng với tình trạng sức khỏe kém của đàn bò, Farmer John đăng ký cho chúng tham gia nhiều hoạt động rèn luyện thể chất khác nhau. Cô bò quý Bessie của ông tham gia một lớp chạy bộ, nơi cô được kỳ vọng cuối cùng sẽ chạy một cuộc marathon qua khu trung tâm của thành phố gần trang trại của Farmer John!
Đường chạy marathon gồm \(N\) checkpoint (\(3 \le N \le 500\)) phải được ghé thăm theo thứ tự, trong đó checkpoint 1 là điểm xuất phát và checkpoint \(N\) là đích đến. Bessie lẽ ra phải lần lượt đi qua tất cả các checkpoint này, nhưng vì là một cô bò lười biếng, cô quyết định sẽ bỏ qua nhiều nhất \(K\) checkpoint (\(K < N\)) để rút ngắn tổng quãng đường. Tuy nhiên, cô không thể bỏ qua checkpoint 1 hoặc checkpoint \(N\), vì làm vậy sẽ quá dễ bị phát hiện.
Hãy giúp Bessie tìm quãng đường ngắn nhất mà cô phải chạy nếu được bỏ qua nhiều nhất \(K\) checkpoint.
Vì đường chạy nằm trong khu trung tâm với mạng lưới đường phố dạng ô vuông, khoảng cách giữa hai checkpoint tại \((x_1,y_1)\) và \((x_2,y_2)\) được tính bằng \(|x_1-x_2|+|y_1-y_2|\).
Dòng đầu tiên chứa các giá trị \(N\) và \(K\).
\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) cách nhau bởi dấu cách, biểu diễn một checkpoint (\(-1000 \le x \le 1000\), \(-1000 \le y \le 1000\)). Các checkpoint được cho theo đúng thứ tự phải ghé thăm. Lưu ý rằng đường chạy có thể tự cắt nhau nhiều lần, và nhiều checkpoint có thể nằm tại cùng một vị trí thực tế. Khi Bessie bỏ qua một checkpoint như vậy, cô chỉ bỏ qua một lần xuất hiện của checkpoint đó, chứ không bỏ qua mọi checkpoint nằm tại cùng vị trí.
In ra quãng đường ngắn nhất Bessie có thể chạy khi được bỏ qua nhiều nhất \(K\) checkpoint.
Ví dụ 1
5 2
0 0
8 3
1 1
10 -5
2 24Trong ví dụ này, bỏ qua các checkpoint tại \((8,3)\) và \((10,-5)\) cho tổng quãng đường nhỏ nhất là 4.
USACO 2014 December Contest, Silver — Marathon. Tác giả đề: Nick Wu, 2014.
Đàn bò lại ra ngoài vận động móng guốc! Có \(N\) cô bò đang chạy bộ trên một đường chạy một làn dài vô hạn (\(1 \le N \le 100\,000\)). Mỗi cô bò xuất phát tại một vị trí khác nhau trên đường chạy, và một số cô bò chạy với tốc độ khác nhau.
Vì đường chạy chỉ có một làn, các cô bò không thể vượt nhau. Khi một cô bò nhanh hơn bắt kịp một cô bò khác, cô phải chạy chậm lại để tránh đâm vào cô bò phía trước và trở thành một thành viên của cùng nhóm chạy.
Các cô bò sẽ chạy trong \(T\) phút (\(1 \le T \le 1\,000\,000\,000\)). Hãy giúp Farmer John xác định còn lại bao nhiêu nhóm tại thời điểm đó. Hai cô bò được xem là thuộc cùng một nhóm nếu chúng ở cùng vị trí sau khi kết thúc \(T\) phút.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(T\).
\(N\) dòng tiếp theo, mỗi dòng chứa vị trí ban đầu và tốc độ của một cô bò. Vị trí là một số nguyên không âm, còn tốc độ là một số nguyên dương; cả hai số đều không vượt quá 1 tỷ. Tất cả các cô bò xuất phát tại những vị trí khác nhau, và các vị trí này được cho theo thứ tự tăng dần trong dữ liệu vào.
In ra một số nguyên duy nhất cho biết số nhóm còn lại sau \(T\) phút.
Ví dụ 1
5 3
0 1
1 2
2 3
3 2
6 13USACO 2014 December Contest, Silver — Cow Jog. Tác giả đề: Mark Gordon, 2014.