| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016 - Splitting the Field | 100 (p) | 4.0s | 512M |
| 2 | USACO 2016 - Closing the Farm | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - 248 | 100 (p) | 4.0s | 512M |
\(N\) con bò của Farmer John (\(3 \leq N \leq 50\,000\)) đều đứng tại các vị trí phân biệt trên cánh đồng hai chiều của ông. FJ muốn bao quanh tất cả đàn bò bằng một hàng rào hình chữ nhật có các cạnh song song với trục \(x\) và trục \(y\), đồng thời muốn hàng rào này nhỏ nhất có thể nhưng vẫn chứa mọi con bò (bò được phép đứng trên biên).
Không may, FJ đang có ngân sách eo hẹp vì sản lượng sữa thấp trong quý trước. Do đó, ông muốn bao quanh một diện tích nhỏ hơn để giảm chi phí bảo trì, và cách duy nhất ông nghĩ ra để làm điều này là xây hai khu vực có hàng rào thay vì một. Hãy giúp ông tính tổng diện tích cần bao quanh giảm được bao nhiêu khi sử dụng hai khu vực có hàng rào thay vì một. Giống như khu vực ban đầu, hai khu vực này phải cùng nhau chứa tất cả đàn bò (bò được phép đứng trên biên), và các cạnh của chúng phải song song với trục \(x\) và trục \(y\). Hai khu vực không được phép chồng lấn, kể cả trên đường biên. Lưu ý rằng khu vực có diện tích bằng không là hợp lệ, chẳng hạn nếu một khu vực có chiều rộng bằng không và/hoặc chiều cao bằng không.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên xác định vị trí của một con bò. Tọa độ của bò là các số nguyên dương trong khoảng \(1 \ldots 1\,000\,000\,000\).
In một số nguyên duy nhất biểu thị tổng diện tích FJ có thể tiết kiệm được khi sử dụng hai khu vực có hàng rào thay vì một.
Ví dụ 1
6
4 2
8 10
1 1
9 12
14 7
2 3107USACO 2016 US Open Contest, Gold - Splitting the Field: https://usaco.org/index.php?page=viewproblem2&cpid=645
Tác giả: Brian Dean.
Farmer John và đàn bò dự định rời thị trấn để đi nghỉ dài ngày, vì vậy FJ muốn tạm thời đóng cửa trang trại nhằm tiết kiệm tiền trong thời gian đó.
Trang trại gồm \(N\) chuồng được nối với nhau bởi \(M\) đường đi hai chiều giữa một số cặp chuồng (\(1 \leq N, M \leq 200\,000\)). Để đóng cửa trang trại, FJ dự định mỗi lần đóng một chuồng. Khi một chuồng đóng cửa, tất cả các đường đi kề với chuồng đó cũng đóng và không thể được sử dụng nữa.
FJ muốn biết tại mỗi thời điểm (ban đầu và sau mỗi lần đóng cửa) liệu trang trại có "liên thông hoàn toàn" hay không — nghĩa là có thể đi từ bất kỳ chuồng đang mở nào đến bất kỳ chuồng đang mở nào khác theo một dãy đường đi thích hợp. Vì trang trại của FJ ban đầu đang trong tình trạng phần nào xuống cấp, nó thậm chí có thể không liên thông hoàn toàn ngay từ đầu.
Dòng đầu tiên chứa \(N\) và \(M\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đường đi bằng cặp chuồng mà nó nối (các chuồng được đánh số thuận tiện từ \(1 \ldots N\)). \(N\) dòng cuối cùng cho một hoán vị của \(1 \ldots N\), mô tả thứ tự các chuồng sẽ bị đóng cửa.
Kết quả gồm \(N\) dòng, mỗi dòng chứa YES hoặc NO. Dòng đầu tiên cho biết trang trại ban đầu có liên thông hoàn toàn hay không, và dòng \(i+1\) cho biết trang trại có liên thông hoàn toàn hay không sau lần đóng cửa thứ \(i\).
Ví dụ 1
4 3
1 2
2 3
3 4
3
4
1
2YES
NO
YES
YESUSACO 2016 US Open Contest, Gold - Closing the Farm: https://usaco.org/index.php?page=viewproblem2&cpid=646
Tác giả: Yang Liu.
Bessie thích tải trò chơi về điện thoại di động để chơi, mặc dù cô thấy màn hình cảm ứng nhỏ khá bất tiện khi sử dụng bằng những chiếc móng guốc lớn của mình.
Cô đặc biệt bị cuốn hút bởi trò chơi hiện tại. Trò chơi bắt đầu với một dãy gồm \(N\) số nguyên dương (\(2 \leq N \leq 248\)), mỗi số nằm trong khoảng \(1 \ldots 40\). Trong một lượt, Bessie có thể lấy hai số kề nhau có giá trị bằng nhau và thay chúng bằng một số duy nhất có giá trị lớn hơn một đơn vị (ví dụ, cô có thể thay hai số \(7\) kề nhau bằng một số \(8\)). Mục tiêu là tối đa hóa giá trị của số lớn nhất có mặt trong dãy khi trò chơi kết thúc. Hãy giúp Bessie đạt điểm cao nhất có thể!
Dòng đầu tiên chứa \(N\), và \(N\) dòng tiếp theo cho dãy gồm \(N\) số tại thời điểm bắt đầu trò chơi.
In ra số nguyên lớn nhất mà Bessie có thể tạo được.
Ví dụ 1
4
1
1
1
23Trong ví dụ này, đầu tiên Bessie gộp số \(1\) thứ hai và thứ ba để thu được dãy \(1\ 2\ 2\), sau đó cô gộp hai số \(2\) thành một số \(3\). Lưu ý rằng gộp hai số \(1\) đầu tiên không phải là phương án tối ưu.
USACO 2016 US Open Contest, Gold - 248: https://usaco.org/index.php?page=viewproblem2&cpid=647
Tác giả: Mark Chen.