| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - Lifeguards | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Rental Service | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - MooTube | 100 (p) | 4.0s | 512M |
Bác nông dân John đã mở một hồ bơi cho đàn bò vì cho rằng nơi này sẽ giúp chúng thư giãn và sản xuất nhiều sữa hơn.
Để đảm bảo an toàn, ông thuê \(N\) cô bò làm nhân viên cứu hộ, mỗi cô có một ca trực bao phủ một khoảng thời gian liên tục trong ngày. Để đơn giản, mỗi ngày hồ bơi mở cửa từ thời điểm \(t=0\) đến thời điểm \(t=1{,}000{,}000{,}000\), nên mỗi ca trực có thể được mô tả bằng hai số nguyên cho biết thời điểm một cô bò bắt đầu và kết thúc ca trực. Ví dụ, một nhân viên cứu hộ bắt đầu lúc \(t=4\) và kết thúc lúc \(t=7\) sẽ trực trong ba đơn vị thời gian (lưu ý rằng hai đầu mút là các “điểm” thời gian).
Không may, bác nông dân John đã thuê nhiều hơn khả năng chi trả đúng một nhân viên cứu hộ. Biết rằng ông phải sa thải đúng một nhân viên cứu hộ, thời lượng lớn nhất vẫn có thể được bao phủ bởi các ca trực của những nhân viên còn lại là bao nhiêu? Một khoảng thời gian được coi là có người trực nếu có ít nhất một nhân viên cứu hộ hiện diện.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100{,}000\)). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một nhân viên cứu hộ bằng hai số nguyên trong khoảng \(0 \ldots 1{,}000{,}000{,}000\), cho biết thời điểm bắt đầu và kết thúc ca trực của cô. Tất cả các đầu mút này đôi một khác nhau. Ca trực của những nhân viên cứu hộ khác nhau có thể chồng lấn.
In ra một số duy nhất là thời lượng lớn nhất vẫn có thể được bao phủ nếu bác nông dân John sa thải một nhân viên cứu hộ.
Ví dụ 1
3
5 9
1 4
3 77USACO 2018 January Contest, Silver — Lifeguards
Tác giả bài toán: Brian Dean.
Bác nông dân John nhận ra thu nhập từ việc sản xuất sữa không đủ để tài trợ cho sự phát triển của trang trại. Vì vậy, để kiếm thêm tiền, ông mở một dịch vụ cho thuê bò mang tên “USACOW” (đọc là “Use-a-cow”).
Bác nông dân John có \(N\) cô bò (\(1 \leq N \leq 100{,}000\)), mỗi cô có thể sản xuất một lượng sữa nhất định mỗi ngày. Mỗi cửa hàng trong số \(M\) cửa hàng gần trang trại của ông (\(1 \leq M \leq 100{,}000\)) đề nghị mua một lượng sữa nhất định với một mức giá nhất định. Ngoài ra, mỗi người trong số \(R\) nông dân hàng xóm của bác nông dân John (\(1 \leq R \leq 100{,}000\)) muốn thuê một cô bò với một mức giá nhất định.
Bác nông dân John phải chọn vắt sữa hay cho thuê đối với từng cô bò. Hãy giúp ông tìm số tiền lớn nhất có thể kiếm được mỗi ngày.
Dòng đầu tiên chứa \(N\), \(M\) và \(R\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên \(c_i\) (\(1 \leq c_i \leq 1{,}000{,}000\)), cho biết cô bò thứ \(i\) của bác nông dân John có thể sản xuất \(c_i\) gallon sữa mỗi ngày. Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(q_i\) và \(p_i\) (\(1 \leq q_i, p_i \leq 1{,}000{,}000\)), cho biết cửa hàng thứ \(i\) sẵn sàng mua tối đa \(q_i\) gallon sữa với giá \(p_i\) xu mỗi gallon. Lưu ý rằng bác nông dân John có thể bán cho một cửa hàng bất kỳ lượng sữa nào từ \(0\) đến \(q_i\) gallon. Mỗi dòng trong \(R\) dòng tiếp theo chứa một số nguyên \(r_i\) (\(1 \leq r_i \leq 1{,}000{,}000\)), cho biết một người hàng xóm của bác nông dân John muốn thuê một cô bò với giá \(r_i\) xu mỗi ngày.
Kết quả gồm một dòng chứa lợi nhuận lớn nhất bác nông dân John có thể kiếm được mỗi ngày bằng cách vắt sữa hoặc cho thuê từng cô bò. Lưu ý rằng kết quả 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 hơn như long long trong C/C++.
Ví dụ 1
5 3 4
6
2
4
7
1
10 25
2 10
15 15
250
80
100
40725Bác nông dân John nên vắt sữa các cô bò số \(1\) và \(4\) để thu được \(13\) gallon sữa. Ông nên đáp ứng toàn bộ đơn mua \(10\) gallon để kiếm \(250\) xu, rồi bán ba gallon còn lại với giá \(15\) xu mỗi gallon, thu về tổng cộng \(295\) xu từ sữa.
Sau đó, ông nên cho thuê ba cô bò còn lại với giá lần lượt là \(250\), \(80\) và \(100\) xu để kiếm thêm \(430\) xu. (Ông nên bỏ qua đề nghị thuê với giá \(40\) xu.) Tổng lợi nhuận mỗi ngày là \(725\) xu.
USACO 2018 January Contest, Silver — Rental Service
Tác giả bài toán: Jay Leeds.
Trong thời gian rảnh, bác nông dân John đã tạo một dịch vụ chia sẻ video mới mang tên MooTube. Trên MooTube, đàn bò của ông có thể quay, chia sẻ và khám phá nhiều video thú vị. Đàn bò đã đăng \(N\) video (\(1 \leq N \leq 5000\)), được đánh số thuận tiện từ \(1 \ldots N\). Tuy nhiên, bác nông dân John vẫn chưa tìm ra cách giúp đàn bò khám phá những video mới mà chúng có thể yêu thích.
Bác nông dân John muốn tạo một danh sách “video được đề xuất” cho mỗi video trên MooTube. Nhờ đó, đàn bò sẽ được giới thiệu những video liên quan nhất đến các video chúng đã xem.
Bác nông dân John nghĩ ra một thước đo gọi là “độ liên quan”, đúng như tên gọi, dùng để xác định mức độ liên quan giữa hai video. Ông chọn \(N-1\) cặp video và tự tính độ liên quan của từng cặp. Sau đó, ông hình dung các video như một mạng lưới, trong đó mỗi video là một nút và \(N-1\) cặp video mà ông đã xem xét được nối với nhau. Thật thuận tiện, bác nông dân John đã chọn \(N-1\) cặp sao cho từ bất kỳ video nào cũng có đúng một cách để đi theo một đường gồm các liên kết đến bất kỳ video nào khác. Ông quyết định định nghĩa độ liên quan của một cặp video là độ liên quan nhỏ nhất của một liên kết trên đường đi này.
Bác nông dân John muốn chọn một giá trị \(K\) sao cho bên cạnh một video MooTube bất kỳ, tất cả các video khác có độ liên quan với video đó ít nhất là \(K\) đều được đề xuất. Tuy nhiên, ông lo rằng quá nhiều video sẽ được đề xuất cho đàn bò, khiến chúng xao nhãng việc sản xuất sữa! Vì vậy, ông muốn cẩn thận chọn một giá trị \(K\) phù hợp. Bác nông dân John cần bạn giúp trả lời một số câu hỏi về các video được đề xuất ứng với những giá trị \(K\) nhất định.
Dòng đầu tiên chứa \(N\) và \(Q\) (\(1 \leq Q \leq 5000\)).
Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một cặp video mà bác nông dân John tự so sánh. Mỗi dòng chứa ba số nguyên \(p_i\), \(q_i\) và \(r_i\) (\(1 \leq p_i, q_i \leq N\), \(1 \leq r_i \leq 1{,}000{,}000{,}000\)), cho biết video \(p_i\) và video \(q_i\) được nối với nhau bằng một liên kết có độ liên quan \(r_i\).
\(Q\) dòng tiếp theo mô tả \(Q\) câu hỏi của bác nông dân John. Mỗi dòng chứa hai số nguyên \(k_i\) và \(v_i\) (\(1 \leq k_i \leq 1{,}000{,}000{,}000\), \(1 \leq v_i \leq N\)), cho biết câu hỏi thứ \(i\) của ông là có bao nhiêu video sẽ được đề xuất cho người xem video \(v_i\) nếu \(K=k_i\).
In ra \(Q\) dòng. Trên dòng thứ \(i\), in ra câu trả lời cho câu hỏi thứ \(i\) của bác nông dân John.
Ví dụ 1
4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 13
0
2Bác nông dân John xác định video \(1\) và \(2\) có độ liên quan \(3\), video \(2\) và \(3\) có độ liên quan \(2\), còn video \(2\) và \(4\) có độ liên quan \(4\). Từ đó, video \(1\) và \(3\) có độ liên quan \(\min(3,2)=2\), video \(1\) và \(4\) có độ liên quan \(\min(3,4)=3\), còn video \(3\) và \(4\) có độ liên quan \(\min(2,4)=2\).
Bác nông dân John muốn biết có bao nhiêu video được đề xuất từ video \(2\) nếu \(K=1\), từ video \(1\) nếu \(K=3\), và từ video \(1\) nếu \(K=4\). Ta thấy khi \(K=1\), các video \(1\), \(3\) và \(4\) sẽ được đề xuất trên video \(2\). Khi \(K=4\), không có video nào được đề xuất từ video \(1\). Tuy nhiên, khi \(K=3\), các video \(2\) và \(4\) sẽ được đề xuất từ video \(1\).
USACO 2018 January Contest, Silver — MooTube
Tác giả bài toán: Jay Leeds.