ĐỀ THÁNG 1 –LẦN 3
Hãy lập trình giải các bài toán sau:
Câu 1 ( 3 điểm) – NGOẶC ĐƠN
Xét xâu S chỉ bao gồm các ký tự ngoặc mở `(` và ngoặc đóng `)`. Xâu S xác định một cách đặt ngoặc đúng nếu thoã mãn các điều kiện:
- Số ngoặc mở bằng số ngoặc đóng
- Nếu duyệt từ trái sang phải, số lượng ngoặc mở luôn luôn lớn hơn hoặc bằng số lượng ngoặc đóng.
Hãy viết chương trình kiểm tra xem xâu S có xác định một cách đặt ngoặc đúng hay không?
Dữ liệu vào: File văn bản Bai1.inp chứa một xâu S chỉ bao gồm các ký tự ngoặc mở `(` và ngoặc đóng `)`.
Kết quả ra: File văn bản Bai1.out gồm duy nhất từ `Dung` nếu xâu S xác định một cách đặt ngoặc đúng ngược lại thì ghi ký tự `Sai`.
Ví dụ:
Bai1.inp
Bai1.out

((()(())))
Dung

(()()))(())
Sai


Câu 2 ( 4 điểm): TỪ
Cho xâu kí tự S . Tìm từ đầu tiên dài nhất trong xâu (Từ là một dãy kí tự liên tiếp không chứa dấu cách).
+ Dữ liệu vào: file văn bản Bai2.inp chứa xâu S
+ Dữ liệu ra: ghi ra file văn bản Bai2.out là từ đầu tiên dài nhất của xâu S
Ví dụ:
Bai2.inp
Bai2.out

Hoc tin rat thu vi
Hoc

Câu 3 ( 5 điểm): DÃY CON
Cho dãy số nguyên A gồm N phần tử a1, a2, a3, ..., aN (N≤5000, -1000 ≤ a i ≤ 1000). Hãy tìm ra một dãy con của dãy A là dãy tăng nghiêm ngặt có tổng giá trị các phần tử là lớn nhất.
Dữ liệu vào: file văn bản Bai3.inp
+ Dòng 1: Chứa số N
+ Dòng 2: Chứa N số a1, a2, a3, ..., aN mỗi số cách nhau ít nhất một dấu cách.
Dữ liệu ra: file văn bản Bai3.out
+ Dòng 1: ghi tổng giá trị của dãy tìm được
+ Dòng 2: Ghi dãy con tìm được mỗi số cách nhau ít nhất một dấu cách
Ví dụ:
Bai3.inp
Bai3.out

10
2 3 3 7 1 10 6 20 5 4
26
6 20


Câu 4: Mã hóa (3 điểm)
Hãy mã hóa một xâu cho trước theo quy luật sau: A thay bởi Z, B thay bởi Y, C thay bởi X, ... Các kí tự không phải là chữ cái sẽ không thay đổi.
Dữ liệu: ENCO.INP gồm 1 dòng chứa xâu cần mã hóa (có độ dài ≤108). Các kí tự trong xâu chỉ gồm các chữ cái in hoa ‘A’..’Z’ và các kí tự không phải là chữ cái.
Kết quả: Ghi ra file ENCO.OUT xâu đã mã hóa
Ví dụ:
ENCO.INP
ENCO.OUT

GSRH RH Z HVXIVG XLWV.
THIS IS A SECRET CODE.


Câu 5: (5 điểm) Diệt virus
Virus là các đoạn mã được chèn vào chương trình. Không mất tính tổng quát, xem các tệp văn bản là một chương trình. Các đoạn mã Virus có thể chèn vào trong nội dung của chương trình nhiều dạng Virus khác nhau và có thể chèn nhiều lần. Viết chương trình để diệt Virus, với các đoạn mã virus biết trước.
Dữ liệu vào: Trong tệp BAI3.INP:
- Dòng đầu tiên gồm 2 số: k và n;
+ k: là số đoạn mã các dạng virus biết trước;
+ n: là số dòng văn bản của tệp chương trình;
- k dòng tiếp theo là đoạn mã của các dạng virus;
- n dòng cuối là số dòng của tệp chương trình.
Dữ liệu ra: Ghi vào tệp BAI3.OUT:
- Dòng đầu là số virus đã diệt được.
- n dòng tiếp theo là số dòng của tệp chương trình sau khi đã diệt virus.
Ví dụ:
BAI3.INP
BAI3.OUT

4 2
ab12
cc333
e1d
hh21
hab12sg tiabcceabhh2abcc333121121d3ab123312n
loccabccab1233312hhcc3e1hh2ab121d3321333p11
21
hsg tin
lop11


Bài 1: (3 điểm)

STT
Input
Ouput
Điểm

1
((((((((((((
Sai
0,5

2
()()))((
Sai
0,5

3
()()((()))
Dung
0,5

4
()()((()))(()))(()
Sai
0,5

5
((((()))))
Dung
0,5

6
())(((()))))
Sai
0,5

7
((((())((((())))))))
Dung
0,5

...
...................

0,5

12