BOI 2012 - Ngày 1

Một xâu ngoặc đúng được định nghĩa như sau:

• () và [] là các xâu ngoặc đúng.
• Nếu A là một xâu ngoặc đúng thì (A) và [A] cũng là các xâu ngoặc đúng.
• Nếu A và B là các xâu ngoặc đúng thì xâu nối AB cũng là một xâu ngoặc đúng.

Từ một xâu ngoặc đúng chứa ít nhất một cặp ngoặc vuông, người ta thay mọi dấu ngoặc vuông, cả dấu mở [ lẫn dấu đóng ], bằng dấu ngoặc tròn mở (. Xâu thu được gọi là xâu ngoặc hỏng.

Chẳng hạn, (( và ((((())) đều là các xâu ngoặc hỏng. Xâu thứ nhất được tạo từ []. Xâu thứ hai chỉ có thể được tạo từ bốn xâu ngoặc đúng: []((())), ([](())), (([]())) hoặc ((([]))).

Cho một xâu ngoặc hỏng, hãy đếm số xâu ngoặc đúng có thể tạo ra nó bằng phép thay thế trên.

Dữ liệu vào

Dòng đầu chứa số nguyên chẵn \(N\), độ dài của xâu ngoặc hỏng. Dòng thứ hai chứa \(N\) ký tự ( và ), mô tả xâu đó.

Dữ liệu ra

In ra một số nguyên: số xâu ngoặc đúng có thể có, lấy phần dư khi chia cho \(1\,000\,000\,009\).

Ràng buộc

• \(2 \le N \le 30\,000\) và \(N\) chẵn.
• Xâu đã cho là một xâu ngoặc hỏng theo định nghĩa trên.

Phân nhóm

• Các bộ test có \(N \le 50\) chiếm tổng cộng \(20\) điểm.
• Các bộ test có \(N \le 1000\) chiếm tổng cộng \(45\) điểm, bao gồm các bộ test ở mục trên.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

4
((()

2

8
((((((((

14

Nhà mạng Totalphone vừa xây dựng một số trạm thu phát để phủ sóng một đường cao tốc mới. Tuy nhiên, phần mềm của hãng không cho phép điều chỉnh công suất từng trạm riêng lẻ: mọi trạm phải dùng cùng một mức công suất phát.

Để giảm điện năng tiêu thụ, công ty cần biết khoảng cách lớn nhất từ một điểm trên đường cao tốc đến trạm thu phát gần điểm đó nhất. Hãy tính khoảng cách này.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(L\), lần lượt là số trạm thu phát và chiều dài đường cao tốc. Tiếp theo là \(N\) dòng, mỗi dòng chứa hai số nguyên \(x_i,y_i\) biểu diễn tọa độ một trạm.

Các trạm có tọa độ đôi một khác nhau và được liệt kê theo thứ tự không giảm của \(x_i\). Nếu hai trạm có cùng hoành độ thì chúng được liệt kê theo thứ tự tăng của \(y_i\).

Đường cao tốc là đoạn thẳng nối \((0,0)\) với \((L,0)\).

Dữ liệu ra

In ra một số thực: khoảng cách lớn nhất từ một điểm trên đường cao tốc đến trạm thu phát gần nhất. Kết quả được chấp nhận nếu sai số tuyệt đối so với giá trị chính xác không vượt quá \(10^{-3}\).

Ràng buộc

• \(1 \le N \le 10^6\).
• \(1 \le L \le 10^9\).
• \(-10^9 \le x_i,y_i \le 10^9\).

Phân nhóm

• Các bộ test có \(N \le 5000\) chiếm tổng cộng \(25\) điểm.
• Các bộ test có \(N \le 100\,000\) chiếm tổng cộng \(50\) điểm, bao gồm các bộ test ở mục trên.
• Toàn bộ các bộ test chiếm \(100\) điểm.

Ví dụ

2 10
0 0
11 1

5.545455

Lưu ý

Hãy sử dụng kiểu số thực có độ chính xác ít nhất tương đương double khi tính toán; các kiểu có độ chính xác thấp hơn có thể không đáp ứng sai số yêu cầu.

Một người leo núi sống trên một hòn đảo nhiều núi đã lên tới một đỉnh và muốn đi tiếp đến một đỉnh cao hơn.

Mỗi điểm trên đảo có độ cao dương so với mực nước biển, còn mặt biển có độ cao \(0\). Nếu đỉnh hiện tại có độ cao \(E_i\), người leo núi muốn tới một đỉnh có độ cao \(E_j>E_i\). Vì đang đứng trên một đỉnh, anh không thể đi thẳng lên cao hơn mà trước hết phải đi xuống rồi mới leo lên. Anh muốn chọn đường đi sao cho độ cao của điểm thấp nhất trên đường đi là lớn nhất có thể.

Trong hình, nếu bắt đầu từ đỉnh có độ cao \(E_4\), anh có thể tới một trong ba đỉnh cao hơn là \(E_5,E_6,E_7\). Đường tới \(E_7\) là lựa chọn tốt nhất: anh không phải xuống thấp hơn \(E_2\), trong khi các lựa chọn còn lại buộc anh xuống tới \(E_1\). Nếu bắt đầu từ \(E_5\), độ cao thấp nhất tốt nhất là \(E_3\) trên đường tới \(E_6\); nếu bắt đầu từ \(E_6\), giá trị tương ứng là \(E_1\).

Bản đồ đảo là một bảng chữ nhật gồm \(N \times M\) ô vuông. Số ghi trong mỗi ô là độ cao của vùng tương ứng. Hai ô được coi là kề nhau nếu chúng có một điểm chung; vì thế, một ô không nằm ở biên có tám ô kề. Một đường đi là một dãy ô mà hai ô liên tiếp luôn kề nhau.

Một vùng bằng phẳng là một tập gồm một hoặc nhiều ô cùng độ cao, trong đó hai ô bất kỳ được nối với nhau bằng một đường đi chỉ qua các ô của tập. Hai ô kề nhau có cùng độ cao luôn thuộc cùng một vùng bằng phẳng. Một đỉnh là một vùng bằng phẳng mà không ô nào của vùng kề với một ô cao hơn.

Hãy tìm tất cả các đỉnh trên đảo. Với mỗi đỉnh, hãy xác định độ cao lớn nhất có thể của điểm thấp nhất trên một đường đi tới một đỉnh cao hơn. Với các đỉnh có độ cao lớn nhất trên đảo, quy ước kết quả bằng \(0\): người leo núi phải ra biển để tìm một đỉnh cao hơn ở nơi khác.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương \(N,M\), lần lượt là số hàng và số cột của bản đồ. Mỗi dòng trong \(N\) dòng tiếp theo chứa \(M\) số nguyên. Số thứ \(j\) trên dòng thứ \(i\) của phần này là \(E_{ij}\), độ cao của ô ở hàng \(i\), cột \(j\).

Dữ liệu ra

Dòng đầu chứa số nguyên \(P\), số đỉnh tìm được. Mỗi dòng trong \(P\) dòng tiếp theo chứa hai số nguyên: độ cao của một đỉnh và độ cao lớn nhất có thể của điểm thấp nhất trên đường tới một đỉnh cao hơn.

Liệt kê các đỉnh theo thứ tự giảm dần của độ cao. Nếu nhiều đỉnh có cùng độ cao, sắp xếp chúng theo thứ tự giảm dần của giá trị thứ hai.

Ràng buộc

• \(1 \le N,M \le 2000\) và \(N M \le 10^5\).
• \(1 \le E_{ij} \le 10^6\).

Phân nhóm

• Các bộ test có \(N \le 2\) hoặc \(M \le 2\) chiếm \(15\) điểm.
• Các bộ test có \(P \le 500\) chiếm \(50\) điểm.
• Các bộ test có \(P \le 5000\) chiếm \(80\) điểm.
• Toàn bộ các bộ test chiếm \(100\) điểm. Các mức điểm trên là tổng điểm cho những bộ test thỏa điều kiện tương ứng, không phải các phần điểm cộng thêm.

Ví dụ

6 6
21 16 9 11 6 7
21 21 10 14 15 9
18 20 8 9 13 14
11 10 9 9 8 13
8 12 12 14 13 8
7 13 12 9 5 1

4
21 0
15 11
14 13
13 12

5 3
16 14 16
14 14 15
12 17 16
12 13 10
16 11 16

5
17 0
16 15
16 14
16 13
16 13