| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016 - Diamond Collector | 100 (p) | 4.0s | 512M |
| 2 | USACO 2016 - Bull in a China Shop | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - Field Reduction | 100 (p) | 4.0s | 512M |
Bessie, cô bò vốn luôn yêu thích những vật lấp lánh, đã bắt đầu theo đuổi sở thích khai thác kim cương vào thời gian rảnh! Cô đã thu thập được \(N\) viên kim cương (\(N \leq 1000\)) với nhiều kích thước khác nhau và muốn sắp xếp một số viên vào một tủ trưng bày trong chuồng.
Vì Bessie muốn những viên kim cương trong tủ có kích thước tương đối giống nhau, cô quyết định không đặt hai viên kim cương vào tủ nếu kích thước của chúng chênh lệch quá \(K\) (hai viên kim cương có thể được trưng bày cùng nhau nếu kích thước của chúng chênh lệch đúng bằng \(K\)). Cho \(K\), hãy giúp Bessie xác định số viên kim cương tối đa mà cô có thể trưng bày trong tủ.
Dòng đầu tiên chứa \(N\) và \(K\) (\(0 \leq K \leq 10\,000\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa một số nguyên biểu thị kích thước của một viên kim cương. Mọi kích thước đều là số dương và không vượt quá \(10\,000\).
In một số nguyên dương duy nhất cho biết số viên kim cương tối đa mà Bessie có thể trưng bày.
Ví dụ 1
5 3
1
6
4
3
14USACO 2016 US Open Contest, Bronze - Diamond Collector: https://usaco.org/index.php?page=viewproblem2&cpid=639
Tác giả: Nick Wu.
Farmer John cho rằng ngôi nhà của mình cần được trang trí thêm. Khi ghé thăm cửa hàng đồ sứ địa phương, ông tìm thấy một bức tượng bò bằng thủy tinh tinh xảo và quyết định mua nó vì biết rằng nó sẽ vừa vặn hoàn hảo trên bệ lò sưởi nhà mình.
Hình dạng của bức tượng bò được mô tả bằng một lưới ký tự \(N \times N\) như dưới đây (\(3 \leq N \leq 8\)), trong đó các ký tự # là một phần của bức tượng còn các ký tự . thì không.
...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............
Không may, ngay trước khi FJ có thể mua hàng, một con bò đực chạy xuyên qua cửa hàng và làm vỡ không chỉ bức tượng của FJ mà còn nhiều đồ vật bằng thủy tinh khác trên các kệ! Bức tượng của FJ vỡ thành 2 mảnh, rồi nhanh chóng lẫn vào tổng cộng \(K\) mảnh nằm trên sàn (\(3 \leq K \leq 10\)). Mỗi mảnh trong số \(K\) mảnh được mô tả bằng một lưới ký tự \(N \times N\), giống như bức tượng ban đầu.
Hãy giúp FJ xác định hai mảnh nào trong số \(K\) mảnh là những mảnh ông cần dán lại để sửa bức tượng bị vỡ. May mắn thay, khi hai mảnh tượng của ông rơi xuống sàn, chúng không bị xoay hay lật. Vì vậy, để lắp ráp lại, FJ chỉ cần có thể tịnh tiến các mảnh theo chiều ngang và/hoặc chiều dọc rồi chồng chúng lên nhau. Nếu chọn đúng hai mảnh, ông phải có thể làm điều này theo cách khôi phục chính xác bức tượng ban đầu, sao cho mỗi ký tự # trong bức tượng ban đầu được biểu diễn trong đúng một trong hai mảnh (nghĩa là sau khi được tịnh tiến và chồng lên nhau, hai mảnh không được có chung bất kỳ ký tự # nào và hợp của chúng phải tạo thành chính xác hình dạng ban đầu).
FJ có thể tịnh tiến một mảnh theo chiều dọc và/hoặc chiều ngang một số ký tự tùy ý, nhưng không được tịnh tiến xa đến mức bất kỳ ký tự # nào của mảnh nằm ngoài lưới \(N \times N\) ban đầu. Hình dạng của mỗi mảnh không nhất thiết chỉ gồm một vùng ký tự # "liên thông"; tuy nhiên, nếu một mảnh gồm nhiều cụm ký tự # rời nhau thì tất cả các cụm phải được tịnh tiến cùng một khoảng khi toàn bộ mảnh được tịnh tiến.
Dòng đầu tiên chứa \(N\), tiếp theo là \(K\). \(N\) dòng tiếp theo cung cấp lưới ký tự mô tả bức tượng ban đầu của FJ. \(KN\) dòng tiếp theo cung cấp \(K\) lưới ký tự mô tả \(K\) mảnh mà FJ tìm thấy trên sàn.
In một dòng chứa hai số nguyên cách nhau bởi dấu cách, mỗi số nằm trong khoảng \(1 \ldots K\), biểu thị chỉ số của hai mảnh thuộc bức tượng của FJ. Luôn tồn tại đúng một lời giải. Hai số được in ra phải theo thứ tự tăng dần.
Ví dụ 1
4 3
####
#..#
#.##
....
.#..
.#..
##..
....
####
##..
#..#
####
....
.###
.#..
.#..1 3USACO 2016 US Open Contest, Bronze - Bull in a China Shop: https://usaco.org/index.php?page=viewproblem2&cpid=640
Tác giả: Brian Dean.
\(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 đó, nếu có thể, ông muốn xây một khu vực có hàng rào bao quanh còn nhỏ hơn nữa và sẵn sàng bán một con bò trong đàn để thực hiện điều này.
Hãy giúp FJ tính diện tích nhỏ nhất có thể bao quanh bằng hàng rào sau khi loại một con bò khỏi đàn (rồi xây hàng rào khít nhất bao quanh \(N-1\) con bò còn lại).
Trong bài này, hãy coi bò là các điểm và hàng rào là tập hợp gồm bốn đoạn thẳng (tức là đừng coi bò là các "hình vuông đơn vị"). Lưu ý rằng đáp án có thể bằng không, chẳng hạn nếu tất cả những con bò còn lại cùng đứng trên một đường thẳng đứng hoặc ngang. Cuối cùng, vì \(N\) có thể khá lớn, bạn có thể cần cẩn thận khi giải bài để bảo đảm chương trình chạy đủ nhanh!
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 40\,000\).
In một số nguyên duy nhất biểu thị diện tích nhỏ nhất mà FJ có thể bao quanh bằng hàng rào sau khi loại khỏi đàn một con bò được lựa chọn cẩn thận.
Ví dụ 1
4
2 4
1 1
5 2
17 2512USACO 2016 US Open Contest, Bronze - Field Reduction: https://usaco.org/index.php?page=viewproblem2&cpid=641
Tác giả: Brian Dean.