Đề thi học sinh giỏi môn Tin THPT năm 2012

Chia sẻ: Nguyen Ty | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

177
lượt xem 32
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Kì thi học sinh giỏi là kì thi quan trọng đối với mỗi học sinh. Dưới đây là đề thi học sinh giỏi môn Tin lớp 12 năm 2012 giúp các em kiểm tra lại đánh giá kiến thức của mình và có thêm thời gian chuẩn bị ôn tập cho kì thi sắp tới được tốt hơn.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi học sinh giỏi môn Tin THPT năm 2012

Họ tên TS : ......................................................... ... Số BD: ...................... Chữ ký GT 1 : ..................... SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH NINH THUẬN NĂM HỌC 2011 – 2012 Khóa ngày: 17 / 11 / 2011 (Đề thi chính thức) Môn thi: TIN HỌC Lớp 12 THPT Thời gian làm bài: 180 phút (Không kể thời gian phát đề) ĐỀ: (Đề thi có 02 trang) TỔNG QUAN ĐỀ THI STT Tên bài File chương trình File dữ liệu vào File kết quả 1 RẮN HỔ MANG snail.* snail.inp snail.out 2 MA TRẬN VUÔNG ĐỐI XỨNG matrix.* matrix.inp matrix.out 3 ĐỔI TIỀN money.* money.inp money.out Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, Free Pascal ho ặc C++. Bài 1: (6 điểm) RẮN HỔ MANG Một con rắn hổ mang sống trên một lưới vuông 8 x 8 có chứa vài vật cản (là các ô màu đen trong hình vẽ dưới đây). Con rắn di chuyển theo đường thẳng (khi còn có thể di chuyển được). Khi nó gặp vật cản hay gặp biên của lưới vuông, nó sẽ quay sang ô bên trái nó. Nếu nó đối diện với ô đã đi qua, nó dừng hẳn. A B C D E F G H 1 r 2 3 4 5 6 7 8 Đường đi khi luôn quay qua trái (13 ô) Con rắn luôn bắt đầu tại ô A1, và luôn bắt đầu việc di chuyển bằng cách đi hướng xuống dưới. Vị trí các vật cản (tức là các ô đen) được cho biết trước. Yêu cầu :Tìm số ô mà con rắn đi qua cho đến khi không đi được nữa và thỏa con rắn luôn đi về bên trái nó. Ví dụ: Hình vẽ trên cho hình ảnh một lưới vuông với ba ô đen (tại các vị trí A6, E2, F5). Đường đi con rắn luôn đi về bên trái nó là: đi từ A1 đến A5, quay sang trái đến E5. Từ E5 quay sang trái đến E3, quay trái, đi thẳng và dừng ở B3. Con rắn đã đi qua 13 ô. Dữ liệu : Vào từ file văn bản snail.inp Dòng đầu tiên ghi số nguyên dương n là số các ô đen; Trên n dòng tiếp theo, mỗi dòng ghi tọa độ một ô đen dưới dạng Xm , trong đó X (là các chữ cái Latinh viết hoa từ A đến H) chỉ cột và m (1≤m≤ 8) chỉ dòng . Chú ý không có ô đen tại A1 và A2. Trang 1/2 Đề thi chính thức
Kết quả: Ghi ra file văn bản snail.out số ô mà con rắn đi qua Ví Dụ : snail.inp snail.out 3 13 A6 E2 F5 Bài 2: (7 điểm) MA TRẬN VUÔNG ĐỐI XỨNG Cho ma tr ận vuông A kích thư ớc N x N ch ứa các s ố tự nhiên trong kho ảng từ 0 đến 255; 4 ≤ N ≤ 50. Hãy tìm một ma trận vuông đối xứng có kích thước lớn nhất B trong A theo nghĩa các phần tử đối xứng qua đường chéo chính của B thì bằng nhau. Dữ liệu : Vào từ file văn bản matrix.inp Dòng đầu ghi giá trị N. Tiếp đến là N dòng của ma trận A. Dữ liệu trên cùng một dòng cách nhau ít nhất một khoảng trắng. Kết quả : Ghi ra file văn bản matrix.out Gồm một dòng chứa ba giá trị i, j, d cách nhau ít nhất một khoảng trắng, trong đó i, j cho biết vị trí (dòng i, cột j) đầu tiên của ma trận B cần tìm trong ma trận A, còn d cho biết số phần tử trên cùng một dòng của B. Chỉ số dòng và cột được tính từ 1 đến N. (nếu có nhiều ma trận vuông đối xứng cùng kích thước trong A thì chọn một trong số đó). Ví Dụ : matrix.inp matrix.out 4 2 1 3 7 6 8 9 1 2 3 0 2 4 5 7 3 5 6 9 Bài 3: (7 điểm) ĐỔI TIỀN Có n loại tiền từ A1, A2,…..,A n. Hãy tìm cách dùng các loại tiền này để có số tiền L sao cho tổng số tờ tiền là ít nhất. Dữ liệu : Vào từ file money.inp Dòng đầu ghi số nguyên L (10≤ L ≤ 10000). Dòng thứ 2 ghi số n (n ≤ 40). Các dòng tiếp theo ghi giá tr ị của các số a i (a i ≤ 100). Kết quả : Ghi ra file văn bản money.out các dòng chứa hai số k, m theo thứ tự là số lượng và loại tờ tiền (nếu không có cách đổi thì ghi 0). Ví Dụ : money.inp money.out 13 4 2 3 1 5 2 5 10 (Với 13 đồng thì dùng 4 tờ 2 đồng; 1 tờ 5 đồng.) ---Hết--- Trang 2/2 Đề thi chính thức
SỞ GIÁO DỤC VÀ ĐÀO KỲ THI LẬP ĐỘI TUYỂN DỰ THI CHỌN HỌC SINH TẠO GIỎI QUỐC GIA THPT NĂM 2013 - VÒNG 2 TỈNH YÊN BÁI Môn thi: Tin học ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề) (Đề thi có 02 trang, gồm 04 Ngày thi: 12/11/2012 câu) Câu 1. (6 điểm) Bảng số Tên file chương trình CAU1.PAS Trên bảng chữ số gồm M dòng N cột các phần tử nguyên a[i,j]. Hãy sắp xếp các phần tử theo chiều tăng dần trên mỗi hàng từ trái qua phải, sau đó sắp xếp các phần tử theo chiều tăng dần trên mỗi cột từ trên xuống dưới. Ví dụ: Dữ liệu vào: Từ tệp văn bản CAU1.INP gồm: ● Dòng 1: Gồm hai số nguyên M và N (3 ≤ M, N ≤ CAU1.INP CAU1.OUT 100). 45 ● Mỗi dòng trong M dòng tiếp theo có N số 3 9 1 36 12 1 3 7 12 15 nguyên a[i,j], mỗi số ghi cách nhau một dấu cách. 6 4 7 34 12 4 6 8 12 32 6 7 22 32 8 4 7 9 13 34 Dữ liệu ra: Ghi ra tệp văn bản CAU1.OUT gồm M 7 4 9 15 13 6 7 9 22 36 dòng, N cột là các phần tử được sau khi đã sắp xếp như trên. Câu 2. (6 điểm) Chia vật Tên file chương trình CAU2.PAS Trong một gia đình nông dân có bốn người con, khi các con đến tuổi trưởng thành, người cha gọi các con tới và nói: “Cả đời làm lụng vất vả của cha mẹ có tích trữ được một số của cải là các đồ vật có giá trị. Nay muốn chia cho các con…”. Người cha có N đồ vật, đồ vật thứ i có giá trị là a[i]. Người cha muốn chia N đồ vật trên cho 4 người con sao cho độ chênh lệch giữa tổng giá trị các đồ vật mà mỗi người con nhận được là nhỏ nhất. Yêu cầu: Hãy giúp người cha tìm một cách chia N đồ vật theo yêu cầu như trên. Trang 1/2
Dữ liệu vào: Từ tệp văn bản CAU2.INP gồm: Ví dụ  Dòng 1: Số nguyên N là số đồ vật cần chia (4 ≤ N ≤ CAU2.INP CAU2.OUT 100). 7 1  Dòng 2: Gồm N số nguyên a[i] là giá trị của đồ vật 3 12 8 9 5 10 1 6 thứ i 4 2 (1 ≤ a[i] ≤ 100), mỗi số ghi cách nhau một dấu cách. 3 5 Dữ liệu ra: Ghi ra tệp văn bản CAU2.OUT gồm: 4 7  Dòng 1: Chứa độ chênh lệch nhỏ nhất tìm được.  Bốn dòng tiếp theo: Mỗi dòng ghi thứ tự các đồ vật mà người con thứ 1, 2, 3, 4 nhận được. Trang 2/2
Câu 3. (4 điểm) Trò chơi Tên file chương trình CAU3.PAS Trong cuộc thi SV2012, các nhà tài trợ trao cho ban tổ chức N phần thưởng. Mỗi phần thưởng thuộc loại thứ i có khối lượng là A[i] và giá trị C[i]. Số lượng các phần thưởng của mỗi loại không hạn chế. Đội chơi nào chiến thắng trong cuộc thi sẽ được ban tổ chức tặng một cái túi dùng để đựng các phần thưởng và cái túi có thể mang được tối đa khối lượng W. Hỏi các bạn trong đội chơi cần chọn những phần thưởng nào để cho tổng giá trị của các phần thưởng đã chọn là lớn nhất nhưng khối lượng của chúng không vượt quá khối lượng W. Biết mỗi loại phần thưởng có thể hoặc không chọn phần thưởng nào, hoặc chọn một phần thưởng, hoặc chọn nhiều phần thưởng. Dữ liệu vào: Từ tệp văn bản CAU3.INP gồm: Ví dụ: ● Dòng 1: Ghi hai số nguyên N và W (1 ≤ N, W ≤ CAU3.INP CAU3.OUT 1000). 5 13 19 ● N dòng tiếp theo, dòng thứ i ghi hai số nguyên A[i] 3 4 1 1 và C[i] (1 ≤ A[i], C[i] ≤ 1000). 4 5 4 5 5 6 Dữ liệu ra: Ghi ra tệp văn bản CAU3.OUT gồm: 2 3 ● Dòng 1: Ghi tổng giá trị phần thưởng lớn nhất được 1 1 chọn. ● Các dòng tiếp theo ghi chỉ số và số lượng của các loại phần thưởng đã chọn. Giải thích ví dụ: Chọn 1 phần thưởng loại 1, chọn 5 phần thưởng loại 4. Tổng giá trị phần thưởng lớn nhất được chọn là: 1x4 + 3x5 = 19. Câu 4. (4 điểm) Phân phối kênh Tên file chương trình CAU4.PAS Công ty dịch vụ mạng máy tính cần phân phối kênh hoạt động phục vụ N yêu cầu của khách hàng. Các yêu cầu được đánh số từ 1 đến N. Với mỗi khách hàng thứ i ta biết khoảng thời gian yêu cầu sử dụng kênh là (si, ti), i=1, 2, ..., n (khách hàng sẽ sử dụng kênh từ thời điểm si đến thời điểm ti). Thời gian chuyển giao quyền sử dụng kênh từ khách hàng này cho khách hàng khác là không đáng kể. Như vậy, nếu hai khách hàng nào đó được bố trí làm việc trên cùng một kênh thì các khoảng thời gian sử dụng của họ chỉ có thể có nhiều nhất một điểm chung. Yêu cầu: Hãy tìm cách phân phối sử dụng ít kênh nhất. Dữ liệu vào: Từ tệp văn bản CAU4.INP gồm: Ví dụ:  Dòng đầu tiên ghi số nguyên N (1 ≤ N ≤ 200). CAU4.INP CAU4.OUT  Dòng thứ i trong số N dòng tiếp theo ghi 2 số nguyên si 7 3 0 3 45 và ti 3 5 673 (1 ≤ s[i] < t[i] ≤ 1000). 6 8 12 Dữ liệu ra: Ghi ra tệp văn bản với tên CAU4.OUT gồm: 0 7  Dòng đầu tiên ghi số lượng kênh ít nhất cần sử dụng. 7 8  Dòng tiếp theo ghi chỉ số của các khách hàng được sử dụng 0 2 kênh. 2 6 Trang 3/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. Họ và tên thí Số báo danh:………………………………. sinh:……………………………. Giám thị Kí tên:…………………………………….. 1:…………………………………… Giám thị Kí tên:……………………………………. 2:…………………………………… Trang 4/2