| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2016 - 262144 | 100 (p) | 4.0s | 512M |
| 2 | USACO 2016 - Bull in a China Shop | 100 (p) | 4.0s | 512M |
| 3 | USACO 2016 - Landscaping | 100 (p) | 4.0s | 512M |
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 262\,144\)), 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, Platinum - 262144: https://usaco.org/index.php?page=viewproblem2&cpid=648
Tác giả: Mark Chen.
Farmer John quyết định rằng ngôi nhà của ông 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 khít trên bệ phía trên lò sưởi.
Hình dạng của bức tượng bò được mô tả bằng một lưới ký tự kích thước \(N \times M\) như dưới đây (\(3 \leq N, M \leq 500\)), trong đó mỗi ký tự là chữ cái thường thuộc về bức tượng (các chữ cái khác nhau biểu thị các màu khác nhau), còn ký tự . thì không.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
Không may, ngay trước khi FJ kịp mua, 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 \(3\) mảnh, rồi nhanh chóng bị lẫn vào tổng cộng \(K\) mảnh nằm trên sàn (\(4 \leq K \leq 100\)). Mỗi mảnh trong số \(K\) mảnh được mô tả bằng một lưới ký tự, giống như bức tượng ban đầu.
Hãy giúp FJ xác định có bao nhiêu bộ gồm \(3\) mảnh (trong số \(K\) mảnh trên sàn) có thể được dán lại với nhau để phục hồi bức tượng bị vỡ.
Các mảnh trên sàn có thể đã bị lật theo chiều dọc hoặc chiều ngang, hoặc xoay một bội số nào đó của \(90\) độ. Do đó, với lưới ban đầu cùng \(K\) lưới mô tả các mảnh, cần tìm các bộ gồm \(3\) mảnh có thể ghép lại để tạo thành hình ban đầu; được phép tịnh tiến, lật hoặc xoay các mảnh theo các bội số của \(90\) độ. Khi chồng lên nhau, \(3\) mảnh phải tạo thành chính xác hình ban đầu, và mỗi ô có màu trong hình ban đầu phải được biểu diễn trong đúng một mảnh.
Dòng đầu tiên chứa một số nguyên \(K\). Tiếp theo là \(K + 1\) phần mô tả mảnh. Phần mô tả đầu tiên là bức tượng bò bằng thủy tinh ban đầu, còn \(K\) phần mô tả sau là các mảnh vỡ.
Mỗi phần mô tả bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\) (\(1 \leq R, C \leq 100\)). \(R\) dòng tiếp theo chứa \(C\) ký tự chữ cái thường mô tả màu của mỗi ô. Mỗi mảnh liên thông theo chiều ngang/dọc và có ít nhất một ô không rỗng.
In số bộ ba \(i, j, k\) (\(i < j < k\)) sao cho các mảnh \(i\), \(j\) và \(k\) có thể được sắp xếp để tạo thành bức tượng bò bằng thủy tinh ban đầu.
Ví dụ 1
5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..3Ba cách ghép sử dụng các mảnh \((0, 1, 2)\), \((0, 2, 4)\) và \((1, 3, 4)\).
Lưu ý rằng bài này có giới hạn thời gian là \(6\) giây cho mỗi test (và gấp đôi thời gian đó đối với bài nộp bằng Java và Python).
USACO 2016 US Open Contest, Platinum - Bull in a China Shop: https://usaco.org/index.php?page=viewproblem2&cpid=649
Tác giả: Brian Dean.
Farmer John đang xây dựng một khu vườn được tạo cảnh quan đẹp mắt và cần di chuyển một lượng lớn đất trong quá trình này.
Khu vườn gồm một dãy \(N\) luống hoa (\(1 \leq N \leq 100\,000\)), trong đó ban đầu luống hoa \(i\) chứa \(A_i\) đơn vị đất. Farmer John muốn tạo lại cảnh quan khu vườn sao cho mỗi luống hoa \(i\) chứa \(B_i\) đơn vị đất. Tất cả các giá trị \(A_i\) và \(B_i\) đều là số nguyên trong khoảng \(0 \ldots 10\).
Để tạo cảnh quan cho khu vườn, Farmer John có một số lựa chọn: ông có thể mua một đơn vị đất và đặt nó vào một luống hoa tùy chọn với chi phí \(X\) đơn vị tiền; ông có thể lấy một đơn vị đất ra khỏi một luống hoa tùy chọn rồi chuyển nó đi nơi khác với chi phí \(Y\) đơn vị tiền; hoặc ông có thể vận chuyển một đơn vị đất từ luống hoa \(i\) đến luống hoa \(j\) với chi phí bằng \(Z\) nhân với \(|i-j|\). Hãy tính tổng chi phí nhỏ nhất để Farmer John hoàn thành dự án tạo cảnh quan.
Dòng đầu tiên chứa \(N\), \(X\), \(Y\) và \(Z\) (\(0 \leq X, Y \leq 10^8\); \(0 \leq Z \leq 1000\)). Dòng \(i+1\) chứa hai số nguyên \(A_i\) và \(B_i\).
In ra tổng chi phí nhỏ nhất mà FJ cần bỏ ra để tạo cảnh quan.
Ví dụ 1
4 100 200 1
1 4
2 3
3 2
4 0210Lưu ý rằng bài này đã từng xuất hiện trong một kỳ thi USACO trước đây ở bảng Silver; tuy nhiên, các giới hạn trong phiên bản hiện tại đã được tăng lên đáng kể, vì vậy không nên kỳ vọng lời giải cho phiên bản trước, dễ hơn sẽ đạt được nhiều điểm.
USACO 2016 US Open Contest, Platinum - Landscaping: https://usaco.org/index.php?page=viewproblem2&cpid=650
Tác giả: Brian Dean.