Đề thi HSG tin 8

SỞ GIÁO DỤC ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS
BÌNH ĐỊNH KHÓA NGÀY: 18-3-2015

ĐỀ CHÍNH THỨC Môn thi: TIN HỌC
Thời gian: 150 phút (không kể thời gian phát đề)
Ngày thi: 18/3/2015

Tổng quan bài thi:
Bài
Tên bài
Tên tệp
chương trình
Tên tệp
dữ liệu vào
Tên tệp
dữ liệu ra

1
Liên phân số
LIENPS.PAS
Nhập từ
bàn phím
Xuất trên
màn hình

2
Số nguyên tố cùng nhau
NTCN.PAS
NTCN.INP
NTCN.OUT

3
Tìm đường hái quả
HAIQUA.PAS
HAIQUA.INP
HAIQUA.OUT


Bài 1: Liên phân số (7,0 điểm):
Số hữu tỉ dương a/b luôn được biểu diễn dưới dạng một liên phân số hữu hạn:


Liên phân số này ký hiệu là [q0,q1,q2,...,qn], trong đó q0(0; q1,q2,...,qn là những số nguyên dương; qn>1; n gọi là độ dài của liên phân số.
Hãy viết chương trình biến đổi một phân số a/b thành liên phân số hữu hạn.
Dữ liệu vào là hai số nguyên dương a, b nhập từ bàn phím để biểu diễn phân số a/b.
Dữ liệu ra là một dòng gồm các số q0,q1,q2,...,qn biểu diễn dạng liên phân số của phân số a/b. Các số viết cách nhau ít nhất một khoảng cách.
Ví dụ:
Input

Output

a=7
b=5

1 2 2


Bài 2: Số nguyên tố cùng nhau: (7,0 điểm):
Hai số nguyên dương được gọi là nguyên tố cùng nhau nếu ước số chung lớn nhất của chúng bằng 1.
Cho N số nguyên dương A1,A2,...,AN. Gọi M là giá trị lớn nhất trong các số A1,A2,...,AN.
Viết chương trình tìm số nguyên dương X lớn nhất không vượt quá M mà X nguyên tố cùng nhau với tất cả các số A1,A2,...,AN.
Dữ liệu vào là tệp NTCN.Inp có cấu trúc như sau:
- Dòng đầu là số nguyên dương N (N(100).
- N dòng tiếp theo, mỗi dòng chứa một giá trị tương ứng A1,A2,...,AN (Ai(1000;i=1,2,...,N).
Dữ liệu ra là tệp NTCN.Out chứa số nguyên X tìm được thỏa mãn điều kiện của bài toán.
Ví dụ:
NTCN.Inp

NTCN.Out

3
4
12
15

13


Bài 3: Tìm đường hái quả (6,0 điểm):
Một khu vườn hình chữ nhật kích thước MxN được chia thành các ô vuông đơn vị để trồng một loại cây ăn quả. Trên mỗi ô thì số quả tương ứng có thể hái được là A[i,j] (1(i(M; 1(j(N).
Một người khách dạo qua vườn và hái tất cả các quả trên những ô đi qua. Vị trí xuất phát từ ô [1,1] và kết thúc tại ô [M,N] với hành trình là sang ô chung cạnh theo hướng tăng của i hoặc j (sang phải hoặc đi xuống – như hình vẽ). Hãy viết chương trình tìm lộ trình đi của người đó để hái được nhiều quả nhất.
1
3
5
7
2

7
9
4
2
2

2
3
1
6
7

7
4
6
2
5


Dữ liệu vào là tệp HAIQUA.INP có cấu trúc như sau:
- Dòng đầu tiên là hai số M, N nguyên dương cách nhau một khoảng cách (0- M dòng tiếp theo, mỗi dòng gồm N số tương ứng là số quả có thể hái được ở các ô theo thứ tự tại hàng thứ i. Mỗi số cách nhau một khoảng cách.
Dữ liệu ra là tệp HAIQUA.OUT cso cấu trúc như sau:
- Dòng đầu là số quả lớn nhất có thể hái được theo một lộ trình thỏa mãn yêu cầu.
- Dòng tiếp theo gồm M+N-1 số tương ứng là số quả hái ở từng ô theo đường đi để được số quả nhiều nhất. Mỗi số cách nhau ít nhất một khoảng cách.
Ví dụ:
HAIQUA.INP

HAIQUA.OUT

4 5
1 3 5 7 2
7 9 4 2 2
2 3 1 6 7
7 4 6 2 5

41
1 7 9 4 2 6