| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Square Pasture | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Block Game | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - The Cow-Signal | 100 (p) | 4.0s | 512M |
Farmer John đã quyết định cải tạo trang trại để đơn giản hóa hình dạng của nó. Trước đây, đàn bò của ông gặm cỏ trong hai đồng cỏ hình chữ nhật có hàng rào bao quanh. Farmer John muốn thay chúng bằng một đồng cỏ hình vuông duy nhất có kích thước nhỏ nhất nhưng vẫn bao phủ toàn bộ những khu vực trong trang trại từng được hai hàng rào cũ bao quanh.
Hãy giúp Farmer John xác định diện tích nhỏ nhất cần có của đồng cỏ hình vuông mới để khi được đặt ở vị trí thích hợp, nó vẫn có thể bao phủ toàn bộ diện tích từng được hai đồng cỏ hình chữ nhật cũ bao phủ. Các cạnh của đồng cỏ hình vuông phải song song với các trục \(x\) và \(y\).
Dòng đầu tiên mô tả một trong hai đồng cỏ hình chữ nhật ban đầu bằng bốn số nguyên cách nhau bởi dấu cách \(x_1\), \(y_1\), \(x_2\), \(y_2\), mỗi số nằm trong khoảng \(0 \ldots 10\). Góc dưới bên trái của đồng cỏ là điểm \((x_1,y_1)\) và góc trên bên phải là điểm \((x_2,y_2)\), trong đó \(x_2>x_1\) và \(y_2>y_1\).
Dòng thứ hai có cùng định dạng bốn số nguyên như dòng đầu tiên và mô tả đồng cỏ hình chữ nhật ban đầu thứ hai. Đồng cỏ này không chồng lấn và cũng không tiếp xúc với đồng cỏ thứ nhất.
In một dòng chứa diện tích nhỏ nhất cần có của một đồng cỏ hình vuông có thể bao phủ toàn bộ những khu vực ban đầu được hai đồng cỏ hình chữ nhật bao quanh.
Ví dụ 1
6 6 8 8
1 8 4 949Trong ví dụ trên, hình chữ nhật ban đầu thứ nhất có các góc \((6,6)\) và \((8,8)\). Hình thứ hai có các góc \((1,8)\) và \((4,9)\). Bằng cách dựng một hàng rào hình vuông cạnh \(7\) với các góc \((1,6)\) và \((8,13)\), ta vẫn có thể bao quanh các khu vực ban đầu; hơn nữa, đây là phương án tốt nhất vì không thể bao quanh các khu vực ban đầu bằng một hình vuông chỉ có cạnh \(6\). Lưu ý rằng có nhiều cách đặt hợp lệ khác nhau cho hình vuông cạnh \(7\), vì nó có thể được dịch theo chiều dọc một chút.
USACO 2016 December Contest, Bronze — Square Pasture. Tác giả đề: Brian Dean.
Farmer John đang cố dạy đàn bò đọc bằng cách đưa cho chúng một bộ gồm \(N\) bảng ghép vần thường dùng cho trẻ mẫu giáo (\(1 \leq N \leq 100\)). Mỗi mặt của một bảng có một từ và một hình ảnh. Chẳng hạn, một mặt có thể có từ cat cùng hình một con mèo, còn mặt kia có thể có từ dog cùng hình một con chó. Vì vậy, khi các bảng nằm trên mặt đất, có \(N\) từ được hiển thị. Bằng cách lật một số bảng, một bộ \(N\) từ khác có thể được đưa lên trên.
Để giúp đàn bò đánh vần, Farmer John muốn làm một số khối gỗ, mỗi khối được khắc nổi một chữ cái trong bảng chữ cái. Ông muốn làm đủ nhiều khối cho mỗi chữ cái để bất kể bộ \(N\) từ nào đang nằm ngửa trên các bảng, đàn bò đều có thể dùng các khối để ghép tất cả những từ này. Chẳng hạn, nếu \(N=3\) và các từ box, cat, car đang nằm ngửa, đàn bò sẽ cần ít nhất một khối b, một khối o, một khối x, hai khối c, hai khối a, một khối t và một khối r.
Hãy giúp Farmer John xác định số khối tối thiểu cần chuẩn bị cho từng chữ cái trong bảng chữ cái, sao cho bất kể mặt nào của mỗi bảng đang được hiển thị, đàn bò đều có thể ghép tất cả \(N\) từ nhìn thấy được.
Dòng đầu tiên chứa số nguyên \(N\).
\(N\) dòng tiếp theo, mỗi dòng chứa hai từ cách nhau bởi một dấu cách, là hai từ ở hai mặt đối diện của một bảng. Mỗi từ là một xâu gồm không quá \(10\) chữ cái thường.
In \(26\) dòng. Dòng đầu tiên chứa số khối chữ a cần có. Dòng tiếp theo chứa số khối chữ b cần có, và cứ tiếp tục như vậy theo thứ tự bảng chữ cái.
Ví dụ 1
3
fox box
dog cat
car bus2
2
2
1
0
1
1
0
0
0
0
0
0
0
2
0
0
1
1
1
1
0
0
1
0
0Trong ví dụ này, có \(N=3\) bảng, tạo ra \(2^3=8\) khả năng cho bộ từ nằm ngửa:
fox dog car
fox dog bus
fox cat car
fox cat bus
box dog car
box dog bus
box cat car
box cat bus
Ta cần đủ số khối cho mỗi chữ cái trong bảng chữ cái để có thể ghép cả ba từ, bất kể trường hợp nào trong tám trường hợp trên xảy ra.
USACO 2016 December Contest, Bronze — Block Game. Tác giả đề: Viktoriia Schwartz.
Bessie và những người bạn bò đang đóng vai các siêu anh hùng bò yêu thích của mình. Tất nhiên, ai cũng biết rằng bất kỳ siêu anh hùng đúng nghĩa nào cũng cần một tín hiệu để triệu tập họ hành động. Bessie đã vẽ một tín hiệu đặc biệt trên một tờ giấy kích thước \(M \times N\) (\(1 \leq M \leq 10\), \(1 \leq N \leq 10\)), nhưng nó quá nhỏ, quá ư là nhỏ! Bessie muốn phóng đại tín hiệu để nó lớn hơn chính xác \(K\) lần (\(1 \leq K \leq 10\)) theo mỗi chiều.
Tín hiệu chỉ gồm hai ký tự . và X.
Dòng đầu tiên chứa \(M\), \(N\) và \(K\), cách nhau bởi dấu cách.
\(M\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(N\); các xâu này cùng nhau mô tả hình ảnh của tín hiệu.
In \(KM\) dòng, mỗi dòng gồm \(KN\) ký tự, mô tả hình ảnh của tín hiệu đã được phóng đại.
Ví dụ 1
5 4 2
XXX.
X..X
XXX.
X..X
XXX.XXXXXX..
XXXXXX..
XX....XX
XX....XX
XXXXXX..
XXXXXX..
XX....XX
XX....XX
XXXXXX..
XXXXXX..USACO 2016 December Contest, Bronze — The Cow-Signal. Tác giả đề: Nathan Pinsker.