| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2012 - Cow Beauty Pageant (Silver Level) | 100 (p) | 4.0s | 512M |
| 2 | USACO 2012 - Cow Lineup | 100 (p) | 4.0s | 512M |
| 3 | USACO 2012 - Tile Exchanging | 100 (p) | 4.0s | 512M |
Nghe nói xu hướng thời trang mới nhất là những con bò có ba đốm trên da, Farmer John đã mua cả một đàn bò ba đốm. Không may, các xu hướng thời trang thường thay đổi rất nhanh, và mốt thịnh hành nhất hiện nay lại là bò chỉ có một đốm!
FJ muốn giúp đàn bò của mình hợp thời hơn bằng cách sơn từng con sao cho ba đốm của nó hợp thành một. Da của một con bò được biểu diễn bằng một lưới ký tự kích thước \(N \times M\) như sau:
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....
Ở đây, mỗi ký tự X biểu thị một phần của một đốm. Hai ký tự X thuộc cùng một đốm nếu chúng kề nhau theo chiều dọc hoặc chiều ngang (kề nhau theo đường chéo không được tính), vì vậy hình trên có đúng ba đốm. Mọi con bò trong đàn của FJ đều có đúng ba đốm.
FJ muốn dùng ít sơn nhất có thể để hợp nhất ba đốm thành một. Trong ví dụ trên, ông có thể làm được điều này bằng cách chỉ sơn thêm bốn ký tự X (các ký tự mới được đánh dấu bằng * bên dưới để dễ nhìn hơn).
................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....
Hãy giúp FJ xác định số ký tự X mới ít nhất mà ông phải sơn để hợp nhất ba đốm thành một đốm lớn.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách (\(1 \leq N, M \leq 50\)).
\(N\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(M\) gồm các ký tự X và ., mô tả một hàng trong họa tiết trên da bò.
In số ký tự X mới ít nhất cần thêm vào họa tiết đầu vào để thu được một đốm duy nhất.
Ví dụ 1
6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....4Họa tiết trong dữ liệu vào biểu diễn da một con bò với ba đốm riêng biệt. Bốn ký tự X là đủ để nối ba đốm thành một.
USACO 2011 November Contest, Silver Division — Cow Beauty Pageant (Silver Level). Tác giả đề: Brian Dean.
Farmer John đã thuê một nhiếp ảnh gia chuyên nghiệp để chụp ảnh một số con bò của mình. Vì đàn bò của FJ thuộc nhiều giống khác nhau, ông muốn bức ảnh có ít nhất một con bò thuộc mỗi giống phân biệt có trong đàn.
\(N\) con bò của FJ đang đứng tại nhiều vị trí trên một đường thẳng; mỗi con được mô tả bởi một vị trí nguyên (tức tọa độ \(x\)) và một mã giống nguyên. FJ dự định chụp một đoạn liên tiếp các con bò dọc theo đường thẳng. Chi phí của bức ảnh bằng kích thước của nó, tức hiệu giữa tọa độ \(x\) lớn nhất và nhỏ nhất của các con bò nằm trong phạm vi bức ảnh.
Hãy giúp FJ tính chi phí nhỏ nhất của một bức ảnh có ít nhất một con bò thuộc mỗi giống phân biệt xuất hiện trong đàn của ông.
Dòng đầu tiên chứa số lượng bò \(N\) (\(1 \leq N \leq 50\,000\)).
Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên dương cách nhau bởi dấu cách, lần lượt cho biết tọa độ \(x\) và mã giống của một con bò. Cả hai số đều không quá 1 tỷ.
In chi phí nhỏ nhất của một bức ảnh chứa mỗi mã giống phân biệt.
Ví dụ 1
6
25 7
26 1
15 1
22 3
20 1
30 14Có 6 con bò lần lượt ở các vị trí \(25, 26, 15, 22, 20, 30\), với các mã giống tương ứng là \(7, 1, 1, 3, 1, 1\).
Phạm vi từ \(x=22\) đến \(x=26\) (có tổng kích thước bằng 4) chứa mỗi mã giống phân biệt 1, 3 và 7 có trong đàn của FJ.
USACO 2011 November Contest, Silver Division — Cow Lineup. Tác giả đề: Brian Dean.
Farmer John muốn lát lại sàn chuồng bằng một bộ gạch vuông mà ông vừa mua từ cửa hàng Square Mart địa phương (dĩ nhiên nơi này chỉ bán các đồ vật hình vuông). Không may, trước khi mua ông đã đo sai kích thước chuồng, nên giờ ông cần đổi một số viên gạch lấy các viên gạch vuông mới có kích thước khác.
\(N\) viên gạch vuông FJ đã mua có độ dài cạnh là \(A_1 \ldots A_N\). Ông muốn đổi một số viên lấy các viên gạch vuông mới sao cho tổng diện tích của tất cả các viên gạch đúng bằng \(M\). Square Mart hiện có một ưu đãi đặc biệt: một viên gạch có độ dài cạnh \(A_i\) có thể được đổi lấy một viên gạch mới có độ dài cạnh \(B_i\) với chi phí \(|A_i-B_i| \times |A_i-B_i|\) đơn vị. Tuy nhiên, ưu đãi này chỉ áp dụng cho những viên gạch đã mua ban đầu — FJ không được phép đổi một viên gạch mà ông đã nhận được từ việc đổi một viên khác (chẳng hạn, không thể đổi một viên cạnh 3 lấy một viên cạnh 2, rồi lại đổi viên cạnh 2 ấy lấy một viên cạnh 1).
Hãy xác định số tiền ít nhất cần dùng để đổi gạch sao cho tổng diện tích các viên gạch trở thành \(M\). In \(-1\) nếu không thể đạt tổng diện tích \(M\).
Dòng đầu tiên chứa hai số nguyên \(N\) (\(1 \leq N \leq 10\)) và \(M\) (\(1 \leq M \leq 10\,000\)), cách nhau bởi dấu cách.
Mỗi dòng trong \(N\) dòng tiếp theo chứa một trong các số nguyên \(A_1\) đến \(A_N\), mô tả độ dài cạnh của một viên gạch đầu vào (\(1 \leq A_i \leq 100\)).
In chi phí nhỏ nhất để đổi gạch nhằm đạt tổng diện tích \(M\), hoặc \(-1\) nếu điều này là không thể.
Ví dụ 1
3 6
3
3
15Có 3 viên gạch: hai viên hình vuông cạnh 3 và một viên hình vuông cạnh 1. Ta muốn đổi chúng để có tổng diện tích bằng 6.
Đổi một viên vuông cạnh 3 lấy một viên vuông cạnh 2, và viên vuông cạnh 3 còn lại lấy một viên vuông cạnh 1. Khi đó ta có tổng diện tích mong muốn \(4+1+1=6\) với chi phí \(4+1=5\) đơn vị.
USACO 2011 November Contest, Silver Division — Tile Exchanging. Tác giả đề: Ray Li.