Đề thi tin học trẻ Đồng Nai 2010 - Khối THPT

Bài 1 Tìm dấu ngoặc sai (3 điểm)
Gọi S là một xâu gồm các dấu ngoặc mở “(“ và dấu ngoặc đóng “)”. Các dấu ngoặc hợp lệ khi chúng tạo thành các cặp ngoặc đóng mở hợp lệ.
Yêu cầu: tìm số lượng fs các dấu ngoặc không hợp lệ trên xâu S.


Ví dụ
S=’(())()’ fs=0
S=’((()’ fs=2
S=’))((‘ fs=4
Input: Tệp văn bản BRACKET.INP
- Dòng thứ nhất gồm 1 số N là số lượng các xâu (N<15) - N dòng sau, mỗi dòng là một xâu S Output: Tệp văn bản BRACKET.OUT - Mỗi dòng là xâu s và số lượng dấu ngoặc sai, cách nhau bởi 1 khoảng trắng BRACKET.INP 3 (())() ((() ))(( BRACKET.OUT (())() 0 ((() 2 ))(( 4 Bài 2 Hoán vị xâu (3 điểm)
Cho xâu S (độ dài không vượt quá 10) chỉ gồm các kí tự ‘A’ đến ‘Z’ (các kí tự trong xâu S không nhất thiết phải khác nhau). Hãy liệt kê tất cả các hoán vị khác nhau của xâu S
Input: Tệp văn bản PERMUTE.INP
- Xâu S
Output: Tệp văn bản PERMUTE.OUT
- Mỗi dòng là một hoán vị của xâu S
PERMUTE.INP
ABA
PERMUTE.OUT
AAB
ABA
BAA

Bài 3 Chọn số (4 điểm)
Cho mảng A có kích thước N*N gồm các số nguyên không âm. Hãy chọn ra K số sao cho mỗi dòng có nhiều nhất một số được chọn, mỗi cột có nhiều nhất một số được chọn để tổng K số là nhỏ nhất.
Input: Tệp văn bản SELECT.INP
- Dòng thứ nhất gồm 2 số N và K (K<=N<=15)
- N dòng sau, mỗi dòng N số nguyên không âm Aij<10000
Output: Tệp văn bản SELECT.OUT.
- Tổng nhỏ nhất chọn được và cách chọn (chỉ cần một cách)
SELECT.INP
5 4
3 2 3 8 3
2 3 1 1 4
3 1 2 9 2
2 7 1 9 3
6 2 1 7 4
SELECT.OUT
5
A24 A32 A41 A53