Ví dụ:
SEQ.INP SEQ.OUT
9
1 2 8 5 6 7 12 10 11 7 a[1]=1 a[2]=2 a[4]=5 a[5]=6 a[6]=7 a[8]=10 a[9]=11
SỞ GIÁO DỤC – ĐÀO TẠO AN GIANG
ĐỀ THI CHỌN ĐỘI TUYỂN THI HSG CẤP QUỐC GIA Khoá ngày 12/11/2011
Ngày thi thứ nhất: 12/11/2011
Môn thi : TIN HỌC
Thời gian : 180 phút (không kể thời gian phát đề) ĐỀ CHÍNH THỨC
SBD:...PHÒNG :...
TỔNG QUAN NGÀY THI THỨ NHẤT
Tên bài File chương trình File dữ liệu vào File kết quả Bài 1 Số đối xứng gần nhất SYMMETRY.PAS
Bài 2 Tích số lớn nhất của dãy LARGEST.PAS MULTI.INP MULTI.OUT Bài 3 Dãy con tăng SEQUENCE.PAS SEQ.INP SEQ.OUT
Bài 1 : (6 điểm)
Số đối xứng gần nhất
Một số được gọi là số đối xứng khi các chữ số của nó đối xứng qua tâm.
Ví dụ : 44, 212, 73237 là số đối xứng.
Lập chương trình nhập vào một số nguyên dương n (n có số chữ số 100), hãy tìm số đối xứng lớn hơn và gần n nhất.
Ví dụ: + n = 571, số đối xứng lớn hơn và gần 571 nhất là số 575.
+ n = 4231, số đối xứng lớn hơn và gần 4231 nhất là số 4334.
Bài 2 : (6 điểm)
Tích số lớn nhất của dãy
Cho dãy số nguyên dương a[1], a[2],…, a[n]. Tìm trong dãy số trên 5 số mà có tích lớn nhất.
Dữ liệu vào: Đọc file text có tên MULTI.INP
• Dòng 1: chứa số n (5 n 10000) là số phần tử trong dãy.
• Dòng 2: chứa n số nguyên là các phần tử của dãy.
Kết quả: Ghi ra file text có tên MULTI.OUT
• Dòng 1: chứa tích lớn nhất tìm được.
• Dòng 2: chứa 5 số có tích lớn nhất, đưa ra theo thứ tự tăng dần.
Chú ý: Các số trên cùng 1 hàng trong file input và output cách nhau 1 khoảng trắng.
Ví dụ:
MULTI.INP MULTI.OUT MULTI.INP MULTI.OUT
10
1 2 5 1 3 9 8 7 5 9 22680
5 7 8 9 9 8
10 6 9 12 7 11 4 5 83160
7 9 10 11 12
Bài 3 : (8 điểm)
Dãy con tăng
Cho dãy số nguyên A = a1, a2, …, an. (n ≤ 10000, -10000 ≤ ai ≤ 10000). Một dãy con của A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có 2n dãy con.
Yêu cầu: Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất.
Ví dụ: A = (1, 2, 3, 4, 9, 10, 5, 6, 7, 8).
Dãy con đơn điệu tăng dài nhất là: (1, 2, 3, 4, 5, 6, 7, 8).
Dữ liệu (Input) vào từ file văn bản SEQ.INP
• Dòng 1: Chứa số n
• Dòng 2: Chứa n số a1, a2, …, an cách nhau ít nhất một dấu cách
Kết quả (Output) ghi ra file văn bản SEQ.OUT
• Dòng 1: Ghi độ dài dãy con tìm được
• Các dòng tiếp: ghi dãy con tìm được và chỉ số những phần tử được chọn vào dãy con đó.
---Hết---
* Ghi chú:
- Thí sinh không được sử dụng tài liệu - Cán bộ coi thi không giải thích gì thêm
BIỂU ĐIỂM VÀ ĐÁP ÁN ĐỀ THI NGÀY 12/11/2011 KỲ THI CHỌN ĐỘI TUYỂN THI HSG CẤP QUỐC GIA
Khoá ngày 12/11/2011 - Môn : TIN HỌC Bài 1 : (6 điểm)
a. Biểu điểm
- Chương trình thể hiện được hướng giải quyết theo yêu cầu của đề bài : 1 đ - Nhập dữ liệu và rào cãn tốt : 1 đ
- Chương trình xử lý đúng, in ra kết quả đúng và đầy đủ theo yêu cầu đề bài : 4 đ b. Dữ liệu thử
- Thử rào cản
- Bộ thử: n = 897 số đối xứng lớn hơn và gần n nhất là 898 n = 8654 số đối xứng lớn hơn và gần n nhất là 8668 n = 71271 số đối xứng lớn hơn và gần n nhất là 71317
n = 678910111213 số đối xứng lớn hơn và gần n nhất là 678911119876 n = 20212223242526 số đối xứng lớn hơn và gần n nhất là 20212233221202 Bài 2 : (6 điểm)
- File dữ liệu đúng yêu cầu, đọc dữ liệu chính xác : 1 đ - Xuất ra kết quả đúng (có thể trên màn hình) : 4 đ.
- File xuất có kết quả đúng : 1 đ - Bộ thử :
Bài 3 : (8 điểm)
- File dữ liệu đúng yêu cầu, đọc dữ liệu chính xác : 1 đ - Xuất ra kết quả đúng (có thể trên màn hình) : 6 đ.
- File xuất có kết quả đúng : 1 đ - Bộ thử :
Lần thử Multi.inp Multi.out
1 8
10 6 9 12 7 11 4 5 83160
7 9 10 11 12
2 6
10 20 30 7 11 5 462000
7 10 11 20 30 3 12
4 17 19 90 93 2 3 4 94 95 100 18 5358000
2 3 94 95 100
4 7
4 7 9 5 6 10 11 41580
6 7 9 10 11
5 9
93 93 3 4 94 95 10 5 4 772355700
10 93 93 94 95
Lần thử SEQ.INP SEQ.OUT
1 12
13 17 19 90 93 2 3 4 94 95 100 18
8a[1] = 13 a[2] = 17 a[3] = 19 a[4] = 90 a[5] = 93 a[9] = 94 a[10] = 95 a[11] = 100
2 6
19 7 6 10 11 5
3a[2] = 7 a[4] = 10 a[5] = 11
3 7
4 7 9 5 6 10 11
5a[1] = 4 a[2] = 7 a[3] = 9 a[6] = 10 a[7] = 11
4 8
200 180 220 240 120 230 300 400
5a[1] = 200 a[3] = 220 a[4] = 240 a[7] = 300 a[8] = 400
5 5
10 3 2 6 9
3a[2] = 3 a[4] = 6 a[5] = 9
