Kỳ thi học sinh giỏi tỉnh năm học: 2013 - 2014 môn thi: Tin học lớp 12 thời gian: 180 phút (không kể thời gian giao đề)

SỞ GIÁO DỤC VÀ ĐÀO TẠO
THANH HOÁ
 Số báo danh
.
........................
ĐỀ CHÍNH THỨC
KỲ THI HỌC SINH GIỎI TỈNH
Năm học: 2013-2014
Môn thi: Tin học
Lớp 12 THPT
Ngày thi: 20/03/2014
Thời gian: 180 phút (không kể thời gian giao đề)
Đề này có 03 bài, gồm 02 trang.
Tổng quan bài thi:
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Bài 1
Cộng phân số
BAI1.PAS
BAI1.INP
BAI1.OUT
Bài 2
Tìm số lớn
BAI2.PAS
BAI2.INP
BAI2.OUT
Bài 3
Dãy ngoặc đúng
BAI3.PAS
BAI3.INP
BAI3.OUT
Dữ liệu vào là đúng đắn, không cần phải kiểm tra.
Hãy lập trình giải các bài toán sau:
Bài 1: (6 điểm) Cộng phân số
Cho hai phân số và . 
Yêu cầu: Hãy xác định 2 số nguyên dương E và F thỏa mãn 2 điều kiện sau:
+ Điều kiện 1: 
+ Điều kiện 2: là phân số tối giản
Dữ liệu vào: File văn bản BAI1.INP, có cấu trúc:
+ Dòng 1 chứa hai số A và B.
+ Dòng 2 chứa hai số C và D.
	( A, B, C, D là các số nguyên dương và không lớn hơn 10000)
Dữ liệu ra: File văn bản BAI1.OUT
Có một dòng chứa hai số E và F tìm được thỏa mãn hai điều kiện trên. Các số ghi trên một dòng được cách nhau bởi một dấu cách trống.
Ví dụ:
BAI1.INP
BAI1.OUT
2 5
3 6
9 10
Bài 2: (7 điểm) Tìm số lớn
Cho một dãy gồm N các ký tự có mặt trên bàn phím trong đó có ít nhất 4 chữ số. (N< 106).
Yêu cầu: Hãy loại bỏ một số ký tự khỏi dãy sao cho 4 ký tự cuối cùng còn lại theo đúng thứ tự đó tạo nên 1 số lớn nhất.
Dữ liệu vào: File văn bản chứa BAI2.INP chứa N ký tự.
Dữ liệu ra: File văn bản BAI2.OUT chứa 4 chữ số tạo thành số lớn nhất.
Ví dụ:
BAI2.INP
BAI2.OUT
24t5j4r05f704y652k393
7693
Bài 3: (7 điểm) Dãy ngoặc đúng 
Người ta định nghĩa một xâu kí tự gồm các kí tự ‘(’ và ‘)’ là một dãy ngoặc đúng như sau:
Xâu rỗng là một dãy ngoặc đúng.
Nếu X là dãy ngoặc đúng thì (X) cũng là một dãy ngoặc đúng
Nếu X, Y là những dãy ngoặc đúng thì XY cũng là dãy ngoặc đúng.
Những dãy ngoặc sau là những dãy ngoặc đúng:
()(())
((()))
Những dãy ngoặc sau thì không:
)(
(((()))
)()()(
Cho một xâu kí tự T = T1, T2, ..Tn, trong đó Ti là một trong hai kí tự ‘(’ hoặc ‘)’ với mọi i=1..n.  
Yêu cầu: Hãy đếm số cặp i,j (i<j) mà xâu kí tự thu được từ việc ghép các kí tự liên tiếp Ti, Ti+1, ..Tj (giữ nguyên thứ tự) là một dãy ngoặc đúng.
Dữ liệu vào: File văn bản BAI3.INP gồm 2 dòng:
Dòng thứ nhất chứa số n là độ dài của xâu kí tự T (n ≤ 1000).
Dòng thứ 2 chứa xâu kí tự T
Dữ liệu ra: Ghi ra file văn bản BAI3.OUT một số duy nhất là kết quả tìm được.
Ví dụ:
BAI3.INP
BAI3.OUT
10
(()())(()(
5
Cán bộ coi thi không giải thích gì thêm.
----------------------------- Hết -----------------------------
SỞ GIÁO DỤC VÀ ĐÀO TẠO	KỲ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH
 THANH HÓA	Năm học: 2013-2014
Môn thi: Tin học
HƯỚNG DẪN CHẤM
Bài 1: (6 điểm)
Test
File dữ liệu vào
File kết quả ra
Điểm
1
BAI1.INP
BAI1.OUT
1 điểm
2
BAI1.INP
BAI1.OUT
1 điểm
3
BAI1.INP
BAI1.OUT
1 điểm
4
BAI1.INP
BAI1.OUT
1 điểm
5
BAI1.INP
BAI1.OUT
1 điểm
6
BAI1.INP
BAI1.OUT
1 điểm
Bài 2: (7 điểm)
Test
File dữ liệu vào
File kết quả ra
Điểm
1
BAI2.INP
BAI2.OUT
1 điểm
2
BAI2.INP
BAI2.OUT
1 điểm
3
BAI2.INP
BAI2.OUT
1 điểm
4
BAI2.INP
BAI2.OUT
1 điểm
5
BAI2.INP
BAI2.OUT
1 điểm
6
BAI2.INP
BAI2.OUT
1 điểm
7
BAI2.INP
BAI2.OUT
1 điểm
Bài 3: (7 điểm)
Test
File dữ liệu vào
File kết quả ra
Điểm
1
BAI3.INP
BAI3.OUT
1 điểm
2
BAI3.INP
BAI3.OUT
1 điểm
3
BAI3.INP
BAI3.OUT
1 điểm
4
BAI3.INP
BAI3.OUT
1 điểm
5
BAI3.INP
BAI3.OUT
1 điểm
6
BAI3.INP
BAI3.OUT
1 điểm
7
BAI3.INP
BAI3.OUT
1 điểm