Đề thi HSG Tỉnh

(1)

SỞ GIÁO DỤC VÀ ĐÀO TẠO HẢI DƯƠNG KÌ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12 THPT NĂM HỌC 2013 – 2014

MÔN THI: TIN HỌC Thời gian làm bài: 180 phút Ngày thi: 22 tháng 10 năm 2013

(Đề thi gồm 04 trang) TỔNG QUAN VỀ CÁC BÀI THI TRONG ĐỀ

Stt Tên file chương trình Dữ liệu vào Dữ liệu ra

Câu 1 BAI1.* Bàn phím Màn hình

Câu 4 BAI4.* BAI4.INP BAI4.OUT

Câu 5 BAI5.* BAI5.INP BAI5.OUT

(Dấu * được thay thế bằng PAS hoặc CPP tuỳ theo ngôn ngữ lập trình sử dụng là Pascal hoặc C⁺⁺ )

Yêu cầu các thí sinh đọc kỹ phần này:

 Tên các bài nộp phải đúng như trong phần tổng quan: BAI1.PAS, BAI2.PAS, BAI3.PAS, BAI4.PAS, BAI5.PAS nếu viết bằng Pascal, BAI1.CPP, BAI2.CPP, BA3.CPP, BAI4.CPP, BAI5.CPP nếu viết bằng C++

 Đối với câu 1, câu 2, câu 3 (in ra màn hình), thí sinh không được in ra màn hình bất kỳ thông báo nào khác ngoại trừ kết quả tìm được.

 Đối với câu 4, câu 5 (nhập dữ liệu từ file văn bản và in kết quả ra file văn bản) thí sinh đặt tên các file dữ liệu vào/ra theo đúng như phần tổng quan (tên file không có đường dẫn)

Viết chương trình giải các bài toán sau:

Câu 1: (2 điểm)

Trên mặt phẳng toạ độ Oxy cho hai đường thẳng (d1) và (d2) có phương trình tổng quát như sau:

(d1): ax + by = c (d2): dx + ey = f

(x, y là ẩn; a, b, c, d, e, f là các số thực cho trước thoả mãn a²+b² ≠ 0, d²+e² ≠0) Hãy tìm giao điểm của hai đường thẳng trên.

Dữ liệu: Nhập từ bàn phím 6 số thực theo thứ tự a, b, c, d, e, f (không cần kiểm tra dữ liệu nhập)

Kết quả: In ra màn hình:

 Nếu như hai đường thẳng trên cắt nhau thì in ra hai số thực x và y là hoành độ và tung độ của giao điểm hai đường thẳng này với 3 chữ số phần thập phân

1 ĐỀ CHÍNH THỨC

(2)

 Nếu như hai đường thẳng song song thì in ra thông báo ‘SONG SONG’ (không có dấu nháy, chú ý tất cả là chữ hoa)

 Nếu như hai đường thẳng trùng nhau thì in ra thông báo ‘TRUNG NHAU’

(không có dấu nháy, chú ý tất cả là chữ hoa) Ví dụ:

Dữ liệu nhập Kết quả in ra 1 1 1 1 -1 0 0.500 0.500 1 1 1 1 1 2 SONG SONG 1 1 1 2 2 2 TRUNG NHAU

Câu 2: (2,5 điểm)

Trên mặt bàn có N gói kẹo xếp thành một hàng từ trái sang phải có số kẹo lần lượt là a1, a2, ..., an. An được giao nhiệm vụ chia các gói kẹo này thành hai phần: phần thứ nhất lấy một số gói kẹo (có thể là 0) ở bên trái, phần thứ hai là số gói kẹo còn lại (có thể là 0). Ta gọi độ không công bằng của một cách chia là trị tuyệt đối giữa hiệu của tổng số gói kẹo phần thứ nhất với tổng số gói kẹo phần thứ hai. Ví dụ có 5 gói kẹo với số kẹo lần lượt từ trái sang phải là 6, 1, 3, 4, 5 thì có các cách chia sau:

 Cách 1: Phần 1 - 0 gói, phần 2- 5 gói khi đó độ không bằng là |0-(6+1+3+4+5)|

=19

 Cách 2: Phần 1 – 1 gói, phần 2 – 4 gói. Khi đó độ không công bằng là |6- (1+3+4+5)|=7

 Cách 3: Phần 1 – 2 gói, phần 2 – 3 gói. Khi đó độ không công bằng là |(6+1)- (3+4+5)|=5

 Cách 4: Phần 1 – 3 gói, phần 2 – 2 gói. Khi đó độ không công bằng là | (6+1+3)-(4+5)|=1

 Cách 5: Phần 1 – 4 gói, phần 2 – 1 gói. Khi đó độ không công bằng là | (6+1+3+4)-5|=9

 Cách 6: Phần 1 – 5 gói, phần 2 – 0 gói. Khi đó độ không công bằng là | (6+1+4+3+5)-0|=19

Hãy tìm cách chia sao cho độ không công bằng là nhỏ nhất. Trong ví dụ trên là cách chia thứ 4 (độ không công bằng là 1)

Dữ liệu: Nhập từ bàn phím lần lượt các số sau (theo đúng thứ tự): N (N≤10⁶), a1, a2, ..., an (các giá trị ai nguyên dương và không vượt quá 10⁹, không cần kiểm tra dữ liệu nhập)

Kết quả: Ghi ra màn hình một số nguyên duy nhất là độ không công bằng nhỏ nhất Ví dụ:

Dữ liệu nhập Kết quả ra

5 6 1 3 4 5 1

2

(3)

Câu 3: (2 điểm)

Số nguyên dương a được gọi là đẹp nếu như khi viết các chữ số của a trong cơ số 10 theo thứ tự ngược lại ta thu được số b nguyên tố cùng nhau với a (ước chung lớn nhất của a và b bằng 1)

Ví dụ: nếu a = 23 thì b = 32 khi đó a và b có UCLN bằng 1, vậy 23 là số đẹp;

nếu a = 50 thì b = 5 khi đó a và b có UCLN bằng 5, nên 50 không phải là số đẹp.

Đếm xem trong khoảng [1,n] có bao nhiêu số đẹp.

Dữ liệu: Nhập từ bàn phím duy nhất số nguyên dương n ≤ 10⁶ Kết quả: Ghi ra màn hình số lượng số đẹp trong khoảng [1,n]

Ví dụ:

Dữ liệu Kết quả

20 7

Giải thích: Trong ví dụ trên các số đẹp là: 1,10,13, 14, 16, 17, 19.

Câu 4: (2 điểm)

Dãy số Fibonaci là dãy số vô hạn f0, f1, f2, …. Được định nghĩa như sau:

f0=f1=1

fk= fk-1 + fk-2 với mọi k>1.

Nhập dãy n số nguyên dương a1, a2, …, an . Hãy đếm xem trong dãy số trên có bao nhiêu số Fibonaci khác nhau?

Dữ liệu: Vào từ file văn bản BAI4.INP

 Dòng đầu tiên ghi số nguyên dương n ≤ 10⁵

 Dòng thứ hai ghi n số nguyên a1, a2, …, an (1≤ai≤10⁹). Hai số liên tiếp ghi cách nhau ít nhất một dấu cách

Kết quả: Ghi ra file văn bản BAI4.OUT một số nguyên duy nhất là số lượng số Fibonaci khác nhau trong dãy đã cho

Ví dụ:

BAI4.INP BAI4.OUT

6

4 1 1 7 10 8

2

Giải thích: Trong ví dụ trên 2 số Fibonaci là 1, 8 Câu 5: (1,5 điểm)

Người ta lập số nguyên a bằng cách ghép n số nguyên tố đầu tiên với nhau (theo thứ tự).

Ví dụ:

 n=1 ta được số a=2

3

(4)

 ....

Viết chương trình nhập hai số nguyên dương n, k và in ra số nguyên lớn nhất thu được bằng cách xoá đi k chữ số (không nhất thiết liên tiếp) của số a tương ứng với n và giữ nguyên thứ tự các chữ số còn lại.

Dữ liệu: Nhập từ file văn bản BAI5.INP một dòng duy nhất chứa hai số nguyên dương n, k (n≤50000, k không vượt quá độ dài của số a tương ứng với n)

Kết quả: Ghi ra file văn bản BAI5.OUT số nguyên lớn nhất tìm được Ví dụ:

BAI5.INP BAI5.OUT

5 4 71

...HẾT...

Họ và tên thí sinh:...Số báo danh:...

Chữ ký của giám thị 1:...Chữ ký của giám thị 2:...

4