Đề thi và đáp án HSG Tin học 9 tỉnh Thanh Hóa 2013-2014

SỞ GIÁO DỤC VÀ ĐÀO TẠO
THANH HOÁ

ĐỀ 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 (iDữ 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