| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2022 - Closest Cow Wins | 100 (p) | 4.0s | 512M |
| 2 | USACO 2022 - Connecting Two Barns | 100 (p) | 4.0s | 512M |
| 3 | USACO 2022 - Convoluted Intervals | 100 (p) | 4.0s | 512M |
Farmer John sở hữu một trang trại dài dọc theo đường cao tốc, có thể xem như một trục số một chiều. Trên trang trại có \(K\) bãi cỏ (\(1 \leq K \leq 2\cdot 10^5\)); bãi cỏ thứ \(i\) nằm tại vị trí \(p_i\) và có độ ngon \(t_i\) (\(0\le t_i\le 10^9\)). Đối thủ của Farmer John, Farmer Nhoj, đã bố trí \(M\) con bò của mình (\(1 \leq M \leq 2\cdot 10^5\)) tại các vị trí \(f_1 \ldots f_M\). Tất cả \(K+M\) vị trí này là các số nguyên phân biệt trong đoạn \([0,10^9]\).
Farmer John cần chọn \(N\) vị trí (\(1\le N\le 2\cdot 10^5\)), không nhất thiết là số nguyên, để đặt các con bò của mình. Các vị trí này phải khác những vị trí đã bị bò của Farmer Nhoj chiếm, nhưng Farmer John có thể đặt bò tại cùng vị trí với các bãi cỏ.
Người nông dân sở hữu con bò gần một bãi cỏ nhất sẽ được quyền sở hữu bãi cỏ đó. Nếu hai con bò của hai người nông dân cách bãi cỏ một khoảng bằng nhau thì Farmer Nhoj giành được bãi cỏ.
Cho biết vị trí các con bò của Farmer Nhoj cùng vị trí và độ ngon của các bãi cỏ, hãy xác định tổng độ ngon lớn nhất mà các con bò của Farmer John có thể giành được khi được bố trí tối ưu.
Dòng đầu tiên chứa \(K\), \(M\) và \(N\).
\(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(p_i\) và \(t_i\), cách nhau bởi dấu cách.
\(M\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(f_i\).
In ra một số nguyên biểu thị tổng độ ngon lớn nhất. Lưu ý rằng đáp án có thể quá lớn để lưu trong số nguyên 32 bit, vì vậy bạn có thể cần sử dụng số nguyên 64 bit (chẳng hạn long long trong C hoặc C++).
Tất cả các dữ liệu kiểm thử tuân theo các ràng buộc đã nêu.
Ví dụ 1
6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
1136Nếu Farmer John đặt bò tại các vị trí \(11.5\) và \(8\) thì ông có thể giành được tổng độ ngon \(10+12+14=36\).
USACO 2021 December Contest, Silver — Closest Cow Wins. Tác giả: Brian Dean.
Trang trại của Farmer John gồm \(N\) cánh đồng (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \ldots N\). Giữa các cánh đồng có \(M\) đường đi hai chiều (\(0 \leq M \leq 10^5\)), mỗi đường nối một cặp cánh đồng.
Trang trại có hai nhà kho, một ở cánh đồng \(1\) và một ở cánh đồng \(N\). Farmer John muốn đảm bảo có thể đi bộ giữa hai nhà kho theo một dãy đường đi nào đó. Ông sẵn sàng xây thêm tối đa hai đường đi để đạt được mục tiêu này. Do cách bố trí các cánh đồng, chi phí xây một đường đi mới giữa cánh đồng \(i\) và \(j\) là \((i-j)^2\).
Hãy giúp Farmer John xác định chi phí nhỏ nhất cần thiết để hai nhà kho \(1\) và \(N\) có thể đi tới nhau.
Mỗi dữ liệu vào chứa \(T\) bộ dữ liệu con (\(1\le T\le 20\)), tất cả đều phải được giải đúng để giải được toàn bộ dữ liệu.
Dòng đầu tiên chứa \(T\), sau đó là \(T\) bộ dữ liệu con.
Mỗi bộ dữ liệu con bắt đầu bằng hai số nguyên \(N\) và \(M\). Tiếp theo là \(M\) dòng, mỗi dòng chứa hai số nguyên \(i\) và \(j\), biểu thị một đường đi giữa hai cánh đồng khác nhau \(i\) và \(j\). Đảm bảo rằng giữa hai cánh đồng bất kỳ có nhiều nhất một đường đi và tổng \(N+M\) trên tất cả các bộ dữ liệu con không vượt quá \(5 \cdot 10^5\).
In ra \(T\) dòng. Dòng thứ \(i\) chứa một số nguyên duy nhất là chi phí nhỏ nhất cho bộ dữ liệu con thứ \(i\).
Ví dụ 1
2
5 2
1 2
4 5
5 3
1 2
2 3
4 52
1Trong bộ dữ liệu con thứ nhất, phương án tối ưu là nối cánh đồng \(2\) với \(3\) bằng một đường đi và nối cánh đồng \(3\) với \(4\) bằng một đường đi.
Trong bộ dữ liệu con thứ hai, phương án tối ưu là nối cánh đồng \(3\) với \(4\) bằng một đường đi. Không cần đường đi thứ hai.
USACO 2021 December Contest, Silver — Connecting Two Barns. Tác giả: Nick Wu.
Các con bò đang miệt mài sáng tạo ra những trò chơi thú vị mới. Một trong những ý tưởng hiện tại của chúng liên quan đến một tập gồm \(N\) đoạn (\(1\le N\le 2\cdot 10^5\)), trong đó đoạn thứ \(i\) bắt đầu tại vị trí \(a_i\) trên trục số và kết thúc tại vị trí \(b_i \geq a_i\). Cả \(a_i\) và \(b_i\) đều là các số nguyên trong khoảng \(0 \ldots M\), với \(1 \leq M \leq 5000\).
Để chơi trò chơi, Bessie chọn một đoạn nào đó (giả sử là đoạn thứ \(i\)) và cô em họ Elsie chọn một đoạn nào đó (giả sử là đoạn thứ \(j\), có thể trùng với đoạn của Bessie). Với một giá trị \(k\), chúng thắng nếu \(a_i + a_j \leq k \leq b_i + b_j\).
Với mỗi giá trị \(k\) trong khoảng \(0 \ldots 2M\), hãy đếm số cặp có thứ tự \((i,j)\) mà Bessie và Elsie có thể thắng trò chơi.
Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một đoạn bằng hai số nguyên \(a_i\) và \(b_i\).
In ra \(2M+1\) dòng, mỗi dòng ứng với một giá trị \(k\) trong khoảng \(0 \ldots 2M\).
Lưu ý rằng các giá trị đầu ra có thể quá lớn để lưu trong số nguyên 32 bit, vì vậy bạn có thể cần sử dụng số nguyên 64 bit (chẳng hạn long long trong C hoặc C++).
Ví dụ 1
2 5
1 3
2 50
0
1
3
4
4
4
3
3
1
1Trong ví dụ này, riêng với \(k=3\), có ba cặp có thứ tự giúp Bessie và Elsie thắng: \((1,1)\), \((1,2)\) và \((2,1)\).
USACO 2021 December Contest, Silver — Convoluted Intervals. Tác giả: Benjamin Qi.