| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Paired Up | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Bovine Genomics | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Where's Bessie? | 100 (p) | 4.0s | 512M |
Farmer John nhận thấy mỗi con bò của mình sẽ dễ vắt sữa hơn khi có một con bò khác ở gần để động viên tinh thần. Vì vậy, ông muốn chia \(M\) con bò (\(M \leq 1\,000\,000\,000\), \(M\) chẵn) thành \(M/2\) cặp. Sau đó, mỗi cặp bò sẽ được đưa vào một chuồng riêng trong nhà kho để vắt sữa. Việc vắt sữa ở tất cả \(M/2\) chuồng sẽ diễn ra đồng thời.
Mọi chuyện hơi phức tạp hơn vì mỗi con bò của Farmer John có một sản lượng sữa khác nhau. Nếu hai con bò có sản lượng sữa \(A\) và \(B\) được ghép thành một cặp thì cần tổng cộng \(A+B\) đơn vị thời gian để vắt sữa cả hai.
Hãy giúp Farmer John xác định khoảng thời gian ngắn nhất có thể để hoàn tất toàn bộ quá trình vắt sữa, giả sử ông ghép các con bò theo cách tối ưu.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(x\) và \(y\), cho biết FJ có \(x\) con bò, mỗi con có sản lượng sữa \(y\) (\(1 \leq y \leq 1\,000\,000\,000\)). Tổng tất cả các giá trị \(x\) là \(M\), tổng số bò.
In thời gian ngắn nhất cần để vắt sữa đàn bò của FJ, giả sử chúng được ghép cặp tối ưu.
Ví dụ 1
3
1 8
2 5
1 210Ở đây, nếu ghép cặp hai con bò có sản lượng \(8+2\), và ghép cặp hai con có sản lượng \(5+5\), thì cả hai chuồng đều cần \(10\) đơn vị thời gian để vắt sữa. Vì việc vắt sữa diễn ra đồng thời, toàn bộ quá trình sẽ hoàn tất sau \(10\) đơn vị thời gian. Mọi cách ghép cặp khác đều không tối ưu vì sẽ khiến một chuồng cần hơn \(10\) đơn vị thời gian để vắt sữa.
USACO 2017 US Open Contest, Silver — Paired Up. Tác giả đề: Brian Dean.
Farmer John sở hữu \(N\) con bò có đốm và \(N\) con bò không có đốm. Vừa hoàn thành một khóa học về di truyền học ở bò, ông tin rằng các đốm trên bò của mình là do những đột biến trong hệ gen của bò.
Farmer John phải bỏ ra một khoản chi phí rất lớn để giải trình tự hệ gen của đàn bò. Mỗi hệ gen là một chuỗi độ dài \(M\) được tạo bởi bốn ký tự A, C, G và T. Khi căn chỉnh hệ gen của các con bò, ông thu được một bảng như sau, minh họa với \(N=3\):
Vị trí: 1 2 3 4 5 6 7 ... M
Bò đốm 1: A A T C C C A ... T
Bò đốm 2: G A T T G C A ... A
Bò đốm 3: G G T C G C A ... A
Bò không đốm 1: A C T C C C A ... G
Bò không đốm 2: A G T T G C A ... T
Bò không đốm 3: A G T T C C A ... T
Quan sát kỹ bảng này, ông phỏng đoán rằng các vị trí \(2\) và \(4\) đủ để giải thích đặc điểm có đốm. Nghĩa là chỉ cần nhìn vào các ký tự tại hai vị trí này, Farmer John có thể dự đoán con bò nào có đốm và con bò nào không có đốm (chẳng hạn, nếu thấy G và C thì con bò chắc chắn có đốm).
Farmer John tin rằng đặc điểm có đốm không thể được giải thích chỉ bằng một hoặc hai vị trí trong hệ gen, mà phải bằng cách quan sát một tập hợp gồm ba vị trí phân biệt. Hãy giúp ông đếm số tập hợp gồm ba vị trí phân biệt mà mỗi tập hợp có thể giải thích được đặc điểm có đốm.
Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 500\)) và \(M\) (\(3 \leq M \leq 50\)). \(N\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(M\) ký tự, mô tả hệ gen của các con bò đốm. \(N\) dòng cuối mô tả hệ gen của các con bò không đốm.
In số tập hợp gồm ba vị trí phân biệt có thể giải thích đặc điểm có đốm. Một tập hợp gồm ba vị trí giải thích được đặc điểm có đốm nếu chỉ bằng cách quan sát ba vị trí đó trong hệ gen, ta có thể dự đoán hoàn toàn chính xác đặc điểm có đốm trong quần thể bò của Farmer John.
Ví dụ 1
3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT22USACO 2017 US Open Contest, Silver — Bovine Genomics. Tác giả đề: Brian Dean.
Vốn luôn nổi tiếng là người am hiểu công nghệ, Farmer John đang thử nghiệm chiếc máy ảnh định vị bò tự động mới gắn trên máy bay không người lái. Thiết bị này được cho là có thể chụp ảnh cánh đồng rồi tự động xác định vị trí của các con bò. Tiếc rằng máy ảnh không được trang bị một thuật toán tìm bò đủ tốt, vì vậy FJ cần bạn giúp phát triển một thuật toán tốt hơn.
Ảnh chụp từ trên cao trang trại của ông được mô tả bởi một lưới ký tự \(N \times N\), trong đó mỗi ký tự thuộc khoảng \(A \ldots Z\) và biểu thị một trong \(26\) màu có thể có. Farmer John cho rằng cách tốt nhất để định nghĩa một vị trí có thể có bò (PCL) là như sau: PCL là một lưới con hình chữ nhật (có thể là toàn bộ ảnh), có các cạnh song song với các cạnh của ảnh và không nằm trong bất kỳ PCL nào khác (do đó, không có lưới con nhỏ hơn của một PCL cũng là PCL). Ngoài ra, PCL phải thỏa mãn tính chất sau: nếu chỉ xét nội dung bên trong hình chữ nhật và bỏ qua phần còn lại của ảnh, phải có đúng hai màu; một màu tạo thành một vùng liên thông, còn màu kia tạo thành từ hai vùng liên thông trở lên.
Chẳng hạn, một hình chữ nhật có nội dung
AAAAA
ABABA
AAABB
sẽ là một PCL vì các ký tự A tạo thành một vùng liên thông duy nhất còn các ký tự B tạo thành nhiều hơn một vùng liên thông. Cách diễn giải ở đây là một con bò màu A có các đốm màu B.
Một vùng được gọi là "liên thông" nếu ta có thể đi qua toàn bộ vùng bằng cách liên tục di chuyển từ một ô trong vùng sang một ô khác trong vùng theo các bước lên, xuống, trái hoặc phải.
Cho ảnh do máy ảnh của FJ trả về, hãy đếm số PCL.
Dòng đầu tiên chứa \(N\), kích thước của lưới (\(1 \leq N \leq 20\)). \(N\) dòng tiếp theo mô tả ảnh, mỗi dòng gồm \(N\) ký tự.
In số PCL trong ảnh.
Ví dụ 1
4
ABBC
BBBC
AABB
ABBC2Trong ví dụ này, hai PCL là các hình chữ nhật có nội dung
ABB
BBB
AAB
ABB
và
BC
BC
BB
BC
USACO 2017 US Open Contest, Silver — Where's Bessie? Tác giả đề: Brian Dean.