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ứ hai: 13/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Ứ HAI
Tên bài File chương trình File dữ liệu vào File kết quả Bài 4 Sắp xếp việc PLACEMENT.PAS WORK.INP WORK.OUT Bài 5 Xâu mẫu STRINGS.PAS STRINGS.INP STRINGS.OUT
Bài 6 Phát quà GIFTS.PAS NOEN.INP NOEN.OUT
Bài 4 : (6 điểm)
Sắp xếp việc
Có n công việc cần thực hiện trên một máy tính, mỗi việc đòi hỏi đúng 1 giờ máy. Với mỗi việc ta biết thời hạn phải nộp kết quả thực hiện sau khi hoàn thành việc đó và tiền thưởng thu được nếu nộp kết quả trước hoặc đúng thời điểm quy định. Chỉ có một máy tính trong tay, hãy lập lịch thực hiện đủ n công việc trên máy tính sao cho tổng số tiền thưởng thu được lớn nhất với thời gian hoạt động của máy là nhỏ nhất. Giả thiết rằng máy được khởi động vào đầu ca, thời điểm t = 0 và chỉ tắt máy sau khi đã hoàn thành đủ n công việc.
Dữ liệu: vào từ file văn bản WORK.INP
• Dòng 1: chứa số nguyên dương n (3 n 100)
• N dòng tiếp theo: mỗi việc được mô tả bằng 2 số tự nhiên, số thứ nhất là thời hạn giao nộp, số thứ 2 là tiền thưởng. Các số cách nhau bởi dấu cách.
Ví dụ:
WORK.INP Ý nghĩa: cho biết 5 công việc với các nội dung sau 5
2 15 1 17 3 60 1 30 5 120
- Việc thứ nhất không nộp muộn hơn thời điểm 2 (giờ) với tiền thưởng là 15 (ngàn đồng);
- Việc thứ hai không nộp muộn hơn thời điểm 1 (giờ) với tiền thưởng là 17 (ngàn đồng);
- Việc thứ ba không nộp muộn hơn thời điểm 3 (giờ) với tiền thưởng là 60 (ngàn đồng);
- Việc thứ tư không nộp muộn hơn thời điểm 1 (giờ) với tiền thưởng là 30 (ngàn đồng);
- Việc thứ năm không nộp muộn hơn thời điểm 5 (giờ) với tiền thưởng là 120 (ngàn đồng);
Kết quả: Ghi ra file văn bản WORK.OUT
• N dòng đầu tiên, dòng thứ t ghi một số tự nhiên i cho biết việc thứ i được làm trong giờ t
• Dòng cuối cùng ghi tổng số tiền thu được.
Ví dụ:
WORK.OUT Ý nghĩa:
4 1 3 5 2 225
- Giờ thứ 1 thực hiện việc 4 và nộp đúng hạn nên được thưởng 30;
- Giờ thứ 2 thực hiện việc 1 và nộp đúng hạn nên được thưởng 15;
- Giờ thứ 3 thực hiện việc 3 và nộp đúng hạn nên được thưởng 60;
- Giờ thứ 4 thực hiện việc 5 và nộp trước hạn nên được thưởng 120;
- Giờ thứ 5 thực hiện việc 2
- Tổng tiền thưởng thu được do hoàn thành đúng hạn bốn việc 4, 1,3 và 5: 30 + 15 + 60 + 120 = 225
Bài 5 : (7 điểm)
Xâu mẫu
Cho một tệp văn bản f có tên STRINGS.INP chứa các xâu ký tự, mỗi dòng ghi một xâu có chiều dài tối đa 250 ký tự. Xâu đầu tiên được gọi là xâu mẫu s. Hãy viết chương trình đọc xâu mẫu từ tệp văn bản STRINGS.INP ghi vào tệp văn bản g có tên STRINGS.OUT. Sau đó đọc từng xâu x lại của f, với mỗi xâu x cần ghi vào g các thông tin sau:
+ Nội dung xâu x
+ Hai số v và d cách nhau qua dấu cách, trong đó v là vị trí xuất hiện và d là chiều dài lớn nhất đoạn đầu của xâu x trong xâu mẫu s. Nếu không có thì ghi 0 0.
Ví dụ:
STRINGS.INP STRINGS.OUT cabxabcdab
abcd abxbher
cabxabcdab abcd
5 4 abxbher 2 3
STRINGS.INP STRINGS.OUT sadflslagfdtsght
poerq fdtsuk dflslm
sadflslagfdtsght poerq
0 0 fdtsuk 10 4 dflslm 3 5 Bài 6 : (7 điểm)
Phát quà
Nhân dịp lễ Noen ông già Noen phải mang các món quà khác nhau có mã số từ 1..m để tặng cho n em nhỏ mã số 1..n vui lễ Noen ở một làng quê. Trước khi phát quà, mỗi em nhỏ đã viết ra giấy những món quà mà em đó mơ ước. Yêu cầu: Bạn hãy giúp ông già Noen chia các phần quà sao cho mỗi em có đúng 1 phần quà mà em đó yêu thích.
Dữ liệu: vào từ file văn bản NOEN.INP
• Dòng 1: chứa hai số nguyên dương n và m (m n).
• Dòng thứ i trong số n dòng tiếp theo: k b1 b2 .. bk – k là số lượng quà em i yêu thích; b1
b2 .. bk là mã số các món quà em i yêu thích.
Kết quả: Ghi ra file văn bản NOEN.OUT
• v – số em nhỏ đã nhận được quà.
• v dòng tiếp theo mỗi dòng 2 số i b cho biết em I được nhận món quà b Ví dụ:
NOEN.INP NOEN.OUT Ý nghĩa: Có 4 em và 5 món quà: em 1 thích 3 món quà 1, 2 và 5; : em 2 thích 1 món quà 5; : em 3 thích 2 món quà 1 và 4; : em 4 thích 3 món quà 2, 4 và 1.
Phương án phát quà như sau:
11; 2 5; 3 4; 4 2 4 5
3 1 2 5 1 5 2 1 4 3 2 4 1
4 1 1 2 5 3 44 2
---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 13/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)
- 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 : 4 đ.
- File xuất có kết quả đúng : 1 đ Bộ thử :
Bài 2 : (7 đ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 : 5 đ.
- File xuất có kết quả đúng : 1 đ Bộ thử :
Lầnthử WORK.INP WORK.OUT
1
41 15 3 10 5 100 1 27
42 3 1137
2
6 1 12 3 30 2 205 80 2 251 15
35 24 61 155 3
5 2 15 1 7 2 204 50 3 22
13 54 2107
Lầnthử WORK.INP WORK.OUT
4
81 20 3 40 4 100 3 451 22 5 902 26 4 110
24 38 67 51 385 5
73 4 4 33 5 1 21 5 2 123 7
56 72 31 427
Lầnthử STRINGS.INP STRINGS.OUT
1
cabxabcdab abcdabxbher
cabxabcdab abcd5 4
abxbher 2 3
2
sadflslagfdtsght poerq
fdtsuk dflslm
sadflslagfdtsght poerq
0 0 fdtsuk 10 4Dflslm 3 5
3
abchdgdssklfjfjuiewhda fjabc
juiewhtyr wqqw
abchdgdssklfjfjuiewhda fjabc
12 2juiewhtyr 15 6 wqqw 19 1
4
hgdjhgdjakoppadadaskhdaweqop oprew
oppadahe hgdjhg
akoppadadashk fjak
hgdjhgdjakoppadadaskhdaweqop oprew
27 2 oppadahe 11 6hgdjhg 1 6
akoppadadashk 9 11
fjak 0 0
Bài 3 : (7 đ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 : 5 đ.
- File xuất có kết quả đúng : 1 đ Bộ thử :
______________________________
Lầnthử NOEN.INP NOEN.OUT
1 6 7 3 1 4 5 1 42 3 4 4 5 6 7 2 2 1 2 1 7
6 1 1 2 43 3 4 5 5 26 7
2
5 53 3 4 5 2 4 5 1 12 1 2 2 3 4
51 3 2 5 3 14 2 5 4 3
4 4 2 1 2 1 3 2 3 4 2 2 4 1
4 1 1 2 3 3 44 2
4
7 85 1 3 4 5 6 2 2 3
1 83 4 5 6 3 1 2 3 4 4 6 7 8 2 3 4
71 1 2 2 3 84 5 5 3 6 67 4
5
5 63 2 3 6 2 5 6 2 1 5 3 4 5 6 3 1 2 3
51 2 2 5 3 14 4 5 3
