USACO 2012 - Tháng 11 - Hạng Bạc

Bessie là cô bò đang cố gắng gõ một chuỗi ngoặc đơn cân bằng vào máy tính xách tay của cô ta, nhưng cô ta rất vụng về (do móng guốc khá lớn) nên cô ta hay gõ mất các kí tự. Hãy giúp cô ta tính xem có bao nhiêu kí tự trong chuỗi ngoặc đơn cần phải được đổi chiều (có nghĩa là đổi dấu mở ngoặc đơn thành dấu đóng ngoặc đơn, và ngược lại) để chuỗi ban đầu thành chuỗi cân bằng.
Có nhiều cách để định nghĩa một chuỗi ngoặc là “cân bằng.” Cách dễ nhất là số lượng dấu mở ngoặc ‘(‘ bằng số lượng dấu đóng ngoặc ‘)’, và với bất kì chuỗi tiền tố nào, số lượng dấu mở ngoặc đơn ‘(‘ phải lớn hơn hoặc bằng số lượng dấu đóng ngoặc đơn ‘)’. Trong những ví dụ sau đây, những chuỗi ở bên dưới là chuỗi cân bằng:
()
(())
()(()())
Những chuỗi sau đây là chuỗi không cân bằng:
)(
())(
((())))

Input: CLUMSY.INP

• Một chuỗi dấu ngoặc đơn có độ dài tối đa là 100.000 kí tự.

Output: CLUMSY.OUT

• Một số tự nhiên duy nhất là số lượng dấu ngoặc đơn nhỏ nhất cần phải được đổi chiều để biến chuỗi ban đầu thành chuỗi cân bằng.

())(

2

Trang trại của Farmer John là một lưới đồng cỏ kích thước \(N \times N\), trong đó mỗi đồng cỏ chứa một trong hai loại cỏ khác nhau. Để biểu diễn hai loại cỏ này, ta dùng các ký tự ( và ), vì vậy chẳng hạn trang trại của FJ có thể trông như lưới sau:

(())
)()(
)(((
))))

Khi bò Bessie di chuyển quanh trang trại, cô mất \(A\) đơn vị thời gian để đi từ một đồng cỏ sang một đồng cỏ kề bên (một bước về phía bắc, nam, đông hoặc tây) có cùng loại cỏ, hoặc \(B\) đơn vị thời gian để đi sang một đồng cỏ kề bên có loại cỏ khác. Mỗi khi đi từ một đồng cỏ đến một đồng cỏ xa, Bessie luôn sử dụng một dãy bước mất ít thời gian nhất. Hãy tính lượng thời gian lớn nhất mà Bessie có thể cần khi di chuyển giữa một cặp đồng cỏ nào đó trong trang trại.

Dữ liệu vào

• Dòng 1 chứa ba số nguyên: \(N\) (\(1 \le N \le 30\)), \(A\) (\(0 \le A \le 1\,000\,000\)) và \(B\) (\(0 \le B \le 1\,000\,000\)).
• Các dòng \(1..N+1\): mỗi dòng chứa một chuỗi dấu ngoặc có độ dài \(N\). Tổng thể \(N\) dòng này tạo thành một lưới dấu ngoặc kích thước \(N \times N\).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là lượng thời gian lớn nhất mà Bessie có thể dành để di chuyển giữa một cặp đồng cỏ (với điều kiện cô luôn đi theo một lộ trình mất ít thời gian nhất).

Ví dụ

3 1 2
(((
()(
(()

5

Nguồn

USACO 2012 November Contest, Silver — Problem 2: Distant Pastures

Tác giả đề: Brian Dean, 2012.

Farmer John thường đóng dấu những con bò của mình bằng một dấu tròn, nhưng chiếc bàn là đóng dấu của ông đã hỏng nên ông đành đóng lên mỗi con bò một dấu có hình dấu ngoặc (. Trang trại của ông có hai giống bò: Holstein và Guernsey. Ông đóng lên mỗi con bò một dấu có hình dấu ngoặc. Tùy theo hướng con bò đang quay mặt, dấu này có thể trông giống dấu ngoặc mở hoặc dấu ngoặc đóng.

\(N\) con bò của FJ đều đứng thành một hàng, mỗi con quay mặt về một hướng tùy ý, vì vậy các dấu trên chúng trông giống một chuỗi dấu ngoặc có độ dài \(N\). Khi nhìn vào hàng bò này, FJ nhận thấy một quy luật đáng chú ý: nếu ông quét từ trái sang phải chỉ qua các con Holstein (theo thứ tự chúng xuất hiện trong dãy), ông thu được một chuỗi dấu ngoặc cân bằng; hơn nữa, điều tương tự cũng đúng với các con Guernsey! Để xem đây có thực sự là một sự kiện hiếm gặp hay không, hãy giúp FJ tính số cách có thể gán giống cho \(N\) con bò sao cho tính chất này được thỏa mãn.

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:

)(
())(
((())))

Dữ liệu vào

• Dòng 1 chứa một chuỗi dấu ngoặc có độ dài \(N\) (\(1 \le N \le 1000\)).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là số cách FJ có thể gán giống cho các con bò sao cho những con Holstein tạo thành một dãy con dấu ngoặc cân bằng và những con Guernsey cũng vậy. Vì đáp án có thể rất lớn, hãy in phần dư của số này khi chia cho \(2012\) (tức là in số đó modulo \(2012\)). Những cách gán chỉ sử dụng một giống bò vẫn hợp lệ.

Ví dụ

(())

6

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

Nguồn

USACO 2012 November Contest, Gold — Problem 1: Balanced Cow Breeds

Tác giả đề: Brian Dean, 2012.