| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - Rest Stops | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Snow Boots | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - Teleportation | 100 (p) | 4.0s | 512M |
Bác nông dân John và huấn luyện viên riêng của ông, Bessie, đang leo núi Vancowver. Đối với mục đích của họ (và của bạn), ngọn núi có thể được biểu diễn bằng một đường mòn thẳng dài \(L\) mét (\(1 \leq L \leq 10^6\)). Bác nông dân John sẽ đi trên đường mòn với tốc độ không đổi \(r_F\) giây trên mỗi mét (\(1 \leq r_F \leq 10^6\)). Vì đang rèn luyện sức bền, ông sẽ không dừng nghỉ ở bất kỳ trạm nào dọc đường.
Tuy nhiên, Bessie được phép dừng tại các trạm nghỉ, nơi cô có thể tìm thấy một ít cỏ ngon. Dĩ nhiên, cô không thể dừng ở bất cứ đâu! Có \(N\) trạm nghỉ dọc theo đường mòn (\(1 \leq N \leq 10^5\)); trạm thứ \(i\) cách điểm đầu đường mòn \(x_i\) mét (\(0 < x_i < L\)) và có độ ngon \(c_i\) (\(1 \leq c_i \leq 10^6\)). Nếu Bessie nghỉ tại trạm \(i\) trong \(t\) giây, cô nhận được \(c_i \cdot t\) đơn vị độ ngon.
Khi không ở một trạm nghỉ, Bessie sẽ đi bộ với tốc độ cố định \(r_B\) giây trên mỗi mét (\(1 \leq r_B \leq 10^6\)). Vì Bessie còn trẻ và khỏe mạnh nên \(r_B\) nhỏ hơn \(r_F\) một cách nghiêm ngặt.
Bessie muốn ăn được nhiều cỏ ngon nhất có thể. Nhưng cô lo cho bác nông dân John; cô nghĩ rằng nếu tại bất kỳ thời điểm nào trong chuyến đi, cô ở phía sau bác nông dân John trên đường mòn thì ông có thể mất hết động lực để tiếp tục!
Hãy giúp Bessie tìm tổng số đơn vị độ ngon lớn nhất cô có thể nhận được, đồng thời bảo đảm rằng bác nông dân John hoàn thành chuyến đi.
Dòng đầu tiên chứa bốn số nguyên \(L\), \(N\), \(r_F\) và \(r_B\). \(N\) dòng tiếp theo mô tả các trạm nghỉ. Với mỗi \(i\) từ \(1\) đến \(N\), dòng thứ \(i+1\) chứa hai số nguyên \(x_i\) và \(c_i\), mô tả vị trí của trạm nghỉ thứ \(i\) và độ ngon của cỏ tại đó.
Bảo đảm rằng \(r_F > r_B\) và \(0 < x_1 < \dots < x_N < L\).
Lưu ý rằng \(r_F\) và \(r_B\) được cho theo đơn vị giây trên mỗi mét!
In ra một số nguyên duy nhất: tổng số đơn vị độ ngon lớn nhất Bessie có thể nhận được.
Ví dụ 1
10 2 4 3
7 2
8 115Trong ví dụ này, phương án tối ưu là Bessie dừng \(7\) giây tại trạm nghỉ ở \(x=7\) (nhận được \(14\) đơn vị độ ngon), rồi dừng thêm \(1\) giây tại trạm nghỉ ở \(x=8\) (nhận thêm \(1\) đơn vị độ ngon, tổng cộng là \(15\) đơn vị độ ngon).
USACO 2018 February Contest, Silver — Rest Stops
Tác giả bài toán: Dhruv Rohatgi.
Mùa đông đã đến ở trang trại, và điều đó có nghĩa là tuyết! Có \(N\) ô lát trên con đường từ nhà đến chuồng bò, được đánh số thuận tiện từ \(1 \dots N\), và ô \(i\) bị phủ bởi lớp tuyết sâu \(f_i\) feet.
Bác nông dân John bắt đầu tại ô \(1\) và phải đến ô \(N\) để đánh thức đàn bò. Ô \(1\) được mái nhà che chắn còn ô \(N\) được mái chuồng che chắn, nên cả hai ô này đều không có tuyết. Nhưng để bước lên các ô còn lại, bác nông dân John cần đi ủng!
Trong ba lô dùng khi thời tiết xấu, bác nông dân John có \(B\) đôi ủng, được đánh số từ \(1 \dots B\). Một số đôi chịu được điều kiện khắc nghiệt hơn những đôi khác, còn một số đôi linh hoạt hơn những đôi khác. Cụ thể, đôi \(i\) cho phép bác nông dân John bước vào lớp tuyết sâu tối đa \(s_i\) feet và tiến về phía trước tối đa \(d_i\) ô trong mỗi bước.
Không may, những đôi ủng được xếp theo cách khiến bác nông dân John tại mỗi thời điểm chỉ có thể lấy đôi nằm trên cùng. Vì vậy, vào bất kỳ lúc nào, ông có thể đi đôi ủng trên cùng (vứt bỏ đôi cũ) hoặc vứt bỏ đôi ủng trên cùng (để có thể lấy một đôi mới).
Bác nông dân John chỉ có thể đổi ủng khi đang đứng trên một ô. Nếu ô đó có lớp tuyết sâu \(f\) feet thì cả đôi ủng ông cởi ra VÀ đôi ủng ông đi vào đều phải chịu được lớp tuyết sâu ít nhất \(f\) feet. Những đôi ủng trung gian mà ông vứt đi mà không mang không cần thỏa mãn hạn chế này.
Hãy giúp bác nông dân John giảm thiểu lãng phí bằng cách xác định số đôi ủng ít nhất ông cần vứt bỏ để đến được chuồng bò. Có thể giả sử rằng ban đầu bác nông dân John không đi đôi ủng nào.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi dấu cách (\(2 \leq N,B \leq 250\)).
Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\) là \(f_i\), độ sâu của tuyết trên ô \(i\) (\(0 \leq f_i \leq 10^9\)). Bảo đảm rằng \(f_1 = f_N = 0\).
\(B\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên trên dòng \(i+2\) là \(s_i\), độ sâu tuyết lớn nhất mà đôi ủng \(i\) có thể bước vào. Số nguyên thứ hai trên dòng \(i+2\) là \(d_i\), độ dài bước chân lớn nhất của đôi ủng \(i\). Bảo đảm rằng \(0 \leq s_i \leq 10^9\) và \(1 \leq d_i \leq N-1\).
Các đôi ủng được mô tả theo thứ tự từ trên xuống dưới, nên đôi \(1\) là đôi nằm trên cùng trong ba lô của bác nông dân John, và cứ tiếp tục như vậy.
In ra một số nguyên duy nhất là số đôi ủng ít nhất mà bác nông dân John cần vứt bỏ. Bảo đảm rằng bác nông dân John có thể đến được chuồng bò.
Ví dụ 1
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 12USACO 2018 February Contest, Silver — Snow Boots
Tác giả bài toán: Brian Dean và Dhruv Rohatgi.
Một trong những công việc đồng áng mà bác nông dân John ghét nhất là vận chuyển những lượng lớn phân bò. Để đơn giản hóa quá trình này, ông nghĩ ra một phát minh xuất sắc: máy dịch chuyển phân bò! Thay vì chở phân giữa hai điểm bằng chiếc xe kéo phía sau máy kéo, ông có thể dùng máy dịch chuyển phân để đưa phân tức thời từ vị trí này sang vị trí khác.
Trang trại của bác nông dân John nằm dọc theo một con đường thẳng rất dài, nên mỗi vị trí trong trang trại có thể được mô tả đơn giản bằng vị trí của nó trên con đường này (tương ứng với một điểm trên trục số). Một máy dịch chuyển được mô tả bởi hai số \(x\) và \(y\): phân được đưa đến vị trí \(x\) có thể được dịch chuyển tức thời đến vị trí \(y\).
Bác nông dân John quyết định xây một máy dịch chuyển có đầu thứ nhất đặt tại \(x=0\); nhiệm vụ của bạn là giúp ông xác định cách chọn tốt nhất cho đầu còn lại \(y\). Cụ thể, có \(N\) đống phân trong trang trại của ông (\(1 \leq N \leq 100{,}000\)). Đống thứ \(i\) cần được chuyển từ vị trí \(a_i\) đến vị trí \(b_i\), và bác nông dân John vận chuyển từng đống riêng biệt với các đống khác. Gọi \(d_i\) là quãng đường bác nông dân John lái máy kéo trong lúc chở đống phân thứ \(i\). Khi ông chở trực tiếp đống phân thứ \(i\) bằng máy kéo, ta có thể có \(d_i = |a_i-b_i|\); hoặc \(d_i\) có thể nhỏ hơn nếu ông dùng máy dịch chuyển (chẳng hạn bằng cách dùng máy kéo chở phân từ \(a_i\) đến \(x\), rồi từ \(y\) đến \(b_i\)).
Hãy giúp bác nông dân John xác định giá trị nhỏ nhất có thể của tổng các \(d_i\) bằng cách chọn cẩn thận một vị trí tối ưu để xây đầu còn lại \(y\) của máy dịch chuyển. Cùng một vị trí \(y\) được sử dụng khi vận chuyển mọi đống phân.
Dòng đầu tiên chứa \(N\). Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(a_i\) và \(b_i\), mỗi số là một số nguyên trong khoảng \(-10^8 \ldots 10^8\). Các giá trị này không nhất thiết đôi một khác nhau.
In ra một số duy nhất là tổng nhỏ nhất của các \(d_i\) mà bác nông dân John có thể đạt được. Lưu ý rằng số này có thể quá lớn để lưu trong một số nguyên \(32\) bit tiêu chuẩn, vì vậy bạn có thể cần dùng kiểu số nguyên lớn như long long trong C/C++. Ngoài ra, bạn cũng nên cân nhắc xem đáp án có nhất thiết là một số nguyên hay không...
Ví dụ 1
3
-5 -7
-3 10
-2 710Trong ví dụ này, bằng cách đặt \(y = 8\), bác nông dân John có thể đạt được \(d_1 = 2\), \(d_2 = 5\) và \(d_3 = 3\). Lưu ý rằng mọi giá trị \(y\) trong khoảng \([7,10]\) cũng đều cho một phương án tối ưu.
USACO 2018 February Contest, Silver — Teleportation
Tác giả bài toán: Brian Dean.