| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2013 - Find the Cow! | 100 (p) | 4.0s | 512M |
| 2 | USACO 2013 - Typo | 100 (p) | 4.0s | 512M |
| 3 | USACO 2013 - Horseshoes | 100 (p) | 4.0s | 512M |
Bò Bessie đã trốn thoát và đang ẩn mình trên một sườn đồi phủ đầy cỏ cao. Trong nỗ lực bắt lại Bessie, Farmer John quyết định bò bằng cả tay lẫn đầu gối qua đám cỏ để có thể tiếp cận mà không bị phát hiện. Không may là từ góc nhìn này, ông gặp khó khăn trong việc tìm ra Bessie. Đám cỏ trước mặt Farmer John trông giống như một chuỗi gồm \(N\) dấu ngoặc (\(1 \le N \le 50\,000\)); ví dụ:
)((()())())
Farmer John biết rằng hai chân sau của Bessie trông hệt như một cặp ngoặc mở liền kề ((, còn hai chân trước của cô trông hệt như một cặp ngoặc đóng liền kề )). Vì vậy, vị trí của Bessie có thể được mô tả bởi một cặp chỉ số \(x < y\) sao cho (( xuất hiện tại vị trí \(x\) và )) xuất hiện tại vị trí \(y\). Hãy tính số vị trí khác nhau mà Bessie có thể đang đứng.
(( nằm tại chỉ số \(x\) và mẫu )) nằm tại chỉ số \(y\).Ví dụ 1
)((()())())4Có 4 vị trí mà Bessie có thể đứng, được chỉ ra dưới đây:
1. )((()())())
^^ ^^
2. )((()())())
^^ ^^
3. )((()())())
^^ ^^
4. )((()())())
^^ ^^
USACO 2012 November Contest, Bronze — Problem 1: Find the Cow!
Tác giả đề: Brian Dean, 2012.
Bessie vừa mua một chiếc máy tính xách tay mới, nhưng đáng tiếc là cô không thể gõ thành thạo vì móng guốc lớn của cô quá cỡ so với bàn phím nhỏ. Bessie vừa thử gõ một trong những mẫu yêu thích của mình — một chuỗi dấu ngoặc cân bằng. Tuy nhiên, cô nhận ra rằng mình có thể đã gõ nhầm một ký tự, vô tình thay ( bằng ) hoặc ngược lại. Hãy giúp Bessie tính số vị trí trong chuỗi sao cho việc đảo dấu ngoặc duy nhất tại vị trí đó sẽ làm cho toàn bộ chuỗi trở nên cân bằng.
Có nhiều cách để định nghĩa thế nào là một chuỗi dấu ngoặc "cân bằng". Có lẽ định nghĩa đơn giản nhất là tổng số dấu ( phải bằng tổng số dấu ), và trong mọi tiền tố của chuỗi, số dấu ( phải không ít hơn số dấu ). Ví dụ, các chuỗi sau đều cân bằng:
()
(())
()(()())
trong khi các chuỗi sau thì không:
)(
())(
((())))
Ví dụ 1
()(())))4Nếu quan sát kỹ chuỗi đầu vào:
12345678
()(())))
ta thấy rằng đảo chiều dấu ngoặc ở vị trí 2 tạo ra một chuỗi cân bằng:
12345678
(((())))
Tương tự, đảo dấu ngoặc ở vị trí 5, vị trí 6 hoặc vị trí 7 cũng tạo ra một chuỗi cân bằng.
USACO 2012 November Contest, Bronze — Problem 2: Typo
Tác giả đề: Brian Dean, 2012.
Mặc dù Bessie thấy mọi chuỗi dấu ngoặc cân bằng đều đẹp mắt, cô đặc biệt yêu thích những chuỗi mà mình gọi là cân bằng "hoàn toàn" — gồm một chuỗi các dấu (, theo sau là một chuỗi các dấu ) có cùng độ dài. Ví dụ:
(((())))
Một ngày nọ, khi đi qua chuồng, Bessie phát hiện một lưới móng ngựa kích thước \(N \times N\) trên mặt đất, trong đó mỗi móng ngựa được đặt theo hướng khiến nó trông giống ( hoặc ). Bắt đầu từ góc trên bên trái của lưới, Bessie muốn vừa đi vừa nhặt các móng ngựa sao cho chuỗi cô nhặt được cân bằng hoàn toàn. Hãy giúp cô tính độ dài của chuỗi cân bằng hoàn toàn dài nhất mà cô có thể thu được.
Ở mỗi bước, Bessie có thể di chuyển lên, xuống, sang trái hoặc sang phải. Cô chỉ có thể đi vào một ô lưới đang chứa móng ngựa; khi làm vậy, cô nhặt móng ngựa lên nên không thể quay lại chính ô đó nữa (vì ô ấy không còn móng ngựa). Ban đầu, cô nhặt móng ngựa ở góc trên bên trái của lưới. Bessie chỉ nhặt một dãy móng ngựa tạo thành một chuỗi cân bằng hoàn toàn, vì vậy cô có thể không nhặt được tất cả móng ngựa trong lưới.
0.Ví dụ 1
4
(())
()((
(()(
))))8Thứ tự các bước Bessie đi để thu được một chuỗi cân bằng có độ dài 8 như sau:
1())
2)((
345(
876)
USACO 2012 November Contest, Bronze — Problem 3: Horseshoes
Tác giả đề: Brian Dean, 2012.