USACO 2012 - Tháng 11 - Hạng Vàng

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.

Tất cả bò của Farmer John đều thuộc một giống rất kỳ lạ, nổi tiếng nhờ vẻ ngoài đặc trưng — trên da mỗi con bò có một đốm khổng lồ hình dấu ngoặc (tùy theo hướng con bò đang quay mặt, đốm này có thể trông giống dấu ngoặc mở hoặc dấu ngoặc đóng).

Một buổi sáng, Farmer John xếp bò thành \(K\) hàng, mỗi hàng có \(N\) con (\(1 \le K \le 10\), \(1 \le N \le 50\,000\)). Những con bò quay mặt về các hướng khá tùy ý, vì vậy cách xếp này có thể được mô tả bằng \(K\) chuỗi dấu ngoặc độ dài \(N\) là \(S_1,\ldots,S_K\). Farmer John vô cùng hào hứng nhận thấy một số đoạn bò "đồng thời cân bằng", trong đó một đoạn bò \(i...j\) chỉ đồng thời cân bằng khi mỗi chuỗi \(S_1,\ldots,S_K\) đều cân bằng trên đoạn đó (định nghĩa về một chuỗi dấu ngoặc cân bằng được trình bày bên dưới). Chẳng hạn, nếu \(K=3\) và ta có:

S_1 = )()((())))(())
S_2 = ()(()()()((())
S_3 = )))(()()))(())
                1111
      01234567890123

thì đoạn \([3...8]\) đồng thời cân bằng vì \(S_1[3...8]=((()))\), \(S_2[3...8]=()()()\) và \(S_3[3...8]=(()())\). Các đoạn \([10...13]\) và \([11...12]\) cũng đồng thời cân bằng.

Cho \(K\) chuỗi dấu ngoặc có độ dài \(N\), hãy giúp Farmer John đếm số cặp \((i,j)\) sao cho đoạn \(i...j\) đồng thời 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:

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

Dữ liệu vào

• Dòng 1 chứa hai số nguyên \(K\) và \(N\).
• Các dòng \(2..K+1\): mỗi dòng chứa một chuỗi dấu ngoặc có độ dài \(N\).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là số đoạn đồng thời cân bằng.

Ví dụ

3 14
)()((())))(())
()(()()()((())
)))(()()))(())

3

Nguồn

USACO 2012 November Contest, Gold — Problem 2: Concurrently Balanced Strings

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

Bị cuốn hút bởi những trải nghiệm với dấu ngoặc cân bằng cho đến nay, Farmer John muốn nhờ bạn giúp ông giải một bài toán cuối cùng. Trang trại của FJ có dạng một cây khổng lồ gồm \(N\) đồng cỏ (\(1 \le N \le 40\,000\)), mỗi đồng cỏ được ông gắn nhãn ( hoặc ). Ví dụ:

'('--'('--')'--'('--')'
 |         |
')'       ')'--'('--'('
 |              |
')'            '('--')'--')'--')'--'('

Nhớ rằng vì trang trại của ông là một cây, điều này có nghĩa là một số cặp đồng cỏ được nối với nhau bằng các hành lang sao cho tồn tại đúng một đường đi giữa hai đồng cỏ bất kỳ. FJ tin rằng một số đường đi này biểu diễn các chuỗi dấu ngoặc cân bằng. Cụ thể, trong tất cả những chuỗi cân bằng được biểu diễn bởi các đường đi trên cây, ông muốn biết độ sâu lồng nhau lớn nhất có thể tìm thấy. Độ sâu lồng nhau của một chuỗi dấu ngoặc cân bằng là giá trị lớn nhất, xét trên mọi tiền tố của chuỗi, của số dấu ( dư ra trong tiền tố đó. Ví dụ, chuỗi ()()() có độ sâu lồng nhau bằng 1, nhưng chuỗi ((()))() có độ sâu lồng nhau bằng 3, như có thể thấy rõ khi ta đếm số dấu ( dư ra ở mỗi tiền tố của chuỗi:

((()))()
12321010

Trong trang trại ví dụ ở trên, chuỗi sâu nhất là ((())) với độ sâu 3 và có thể thu được bằng cách đi theo đường từ A đến B dưới đây:

'('--'('--')'--'('--')'
 |         |
')'       ')'--'('--'(' < A
 |              |
')'            '('--')'--')'--')'--'('
 ^C                            ^B

Lưu ý rằng điều này khác với chuỗi cân bằng dài nhất; chẳng hạn, (())(()), bắt đầu tại A và kết thúc tại C, có độ dài 8.

Nhiệm vụ của bạn là in ra độ sâu lồng nhau của đường đi cân bằng sâu nhất trên cây.

Dữ liệu vào

• Dòng 1 chứa một số nguyên duy nhất \(N\), là số đỉnh của cây.
• Các dòng \(2..N\): dòng \(i+1\) chứa một số nguyên duy nhất \(p_{i+1}\) (\(1 \le p_{i+1} \le i\)), biểu thị một cạnh nối đỉnh \(i+1\) với đỉnh \(p_{i+1}\) trên cây.
• Các dòng \(N+1..2N\): dòng \(N+i\) chứa ( hoặc ), là nhãn của đỉnh \(i\).

Dữ liệu ra

• Dòng 1 chứa một số nguyên duy nhất là độ sâu lồng nhau lớn nhất của một đường đi cân bằng.

Ví dụ

15
1
2
1
4
4
6
7
5
9
9
11
12
13
14
(
)
)
(
)
)
(
)
(
(
(
)
)
)
(

3

1'('--4'('--6')'--7'('--8')'
  |     |
2')'  5')'--9'('--10'('
  |           |
3')'       11'('--12')'--13')'--14')'--15'('

Nguồn

USACO 2012 November Contest, Gold — Problem 3: Balanced Trees

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