Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005

Chia sẻ: Lý Hoàng Duy | Ngày: | Loại File: DOC | Số trang:4

Thêm vào BST

Báo xấu

605
lượt xem 109
download

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

Tài liệu tham khảo chuyên môn công nghệ thông tin - Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005

Chủ đề:

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

Lưu

Nội dung Text: Đề thi chọn HSG Tin học 12 cấp Tỉnh năm 2004 - 2005

SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT QUẢNG NGÃI Năm học 2004-2005 Môn: Tin học - Bảng A ĐỀ CHÍNH THỨC Thời gian: 180 phút (không kể thời gian giao đề) Ngày thi: 04/12/2004 TỔNG QUAN BÀI THI NGÀY THỨ NHẤT - BẢNG A Tên bài Tên chương trình Dữ liệu vào Kết quả BÀI 1 Hoán vị thuận thế PERMUTE.PAS Bàn phím Màn hình BÀI 2 Các ký tự LETTERS.PAS LETTERS.INP LETTERS.OUT Hãy lập trình giải các bài toán sau: Bài 1: hoán vị thuận thế Tên chương trình: PERMUTE.PAS Cho a = (a1, a2, ...., aN) là một hoán vị của dãy số tự nhiên 1...N. Ta xây dựng dãy b=(b 1,b2,...,bN) và gọi là thuận thế của hoán vị a như sau: Với mọi i =1..N, bi là số lượng các phần tử nhỏ thua ai và đứng trước ai Ví dụ: N =7 ; a=(6,1,3,5,7,4,2) ta có thuận thế của a là b=(0,0,1,2,4,2,1) a. Cho N và một hoán vị a. Hãy tìm thuận thế của a. b. Cho N và một thuận thế b. Hãy tìm hoán vị sinh ra thuận thế b. Dữ liệu : vào từ bàn phím Đối với câu a: Nhập vào từ bàn phím: số N và một hoán vị a Đối với câu b: Nhập vào từ bàn phím: số N và một thuận thế b. Kết quả: in ra màn hình Đối với câu a: in ra màn hình thuận thế của a Đối với câu b: in ra màn hình hoán vị sinh ra thuận thế b. Ví dụ: Nhập N = 9 a =217654389 Thuận thế của a là : 0 0 2 2 2 2 2 7 8 Nhập N = 9 b=011241558 Hoán vị sinh ra thuận thế b: 1 5 3 4 8 2 7 6 9 Bài 2: Các ký tự Tên chương trình: LETTERS.PAS Trò chơi được mô tả như sau: trên một bảng hình chữ nhật chia R hàng và C cột có các ký tự chữ hoa (A-Z) được viết trên mỗi ô của bảng. Trước khi bắt đầu trò chơi có một hình ở góc trên bên trái của bảng(hàng 1, cột 1). Trong mỗi bước di chuyển, một người chơi có thể di chuyển hình đến vị trí các ô liền kề ( lên trên, xuống dưới, sang trái, sang phải) với ràng buộc rằng hình không thể di 1/2
chuyển đến vị trí kế tiếp nếu ô này chứa ký tự đã xuất hiện mà hình đã di chuyển qua. Mục đích của trò chơi là chơi để có nhiều bước di chuyển nhất có thể được. Viết chương trình xác định số vị trí tối đa trong bảng mà hình có thể viếng thăm trong trò chơi. Dữ liệu: Vào từ tập tin văn bản LETTERS.INP - Dòng thứ nhất chứa hai số nguyên R và C, được viết cách nhau bởi một dấu cách, (1 ≤ R, C ≤ 20 ) - R dòng tiếp theo chứa, mỗi dòng chứa 1 xâu ký tự. Mỗi dòng biểu diễn một hàng của bảng. Kết quả : Ghi vào tập tin văn bản LETTERS.OUT một số nguyên là giá trị lớn nhất các vị trí mà hình có thể di chuyển trên bảng. Ví dụ: letters.inp letters.inp 24 36 CAAB HFDFFB ADCB AJHGDH DGAGEH letters.out letters.out 3 6 Ghi chú: - Thí sinh không được sử dụng tài liệu - Giám thị không giải thích gì thêm. 2/2
SỞ GIÁO DỤC & ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI TỈNH – THPT QUẢNG NGÃI Năm học 2004-2005 HƯỚNG DẪN CHẤM ĐỀ CHÍNH THỨC Môn: Tin học - Bảng A Ngày thi: 04/12/2004 Bài 1: (10 điểm) Test 1 : 1 điểm Test 2 : 1 điểm Test 3 : 2 điểm Test 4 : 2,5 điểm Test 5: 3,5 điểm Hoán vị 217654389 Thuận thế 002222278 Hoán vị sinh ra thuận thế 217654389 Hoán vị 273456819 Thuận thế 011234608 Hoán vị sinh ra thuận thế 273456819 Hoán vị 8 6 3 2 4 11 7 5 9 10 1 Thuận thế 00002543780 Hoán vị sinh ra thuận thế 8 6 3 2 4 11 7 5 9 10 1 Hoán vị 11 9 10 4 5 15 7 1 2 8 14 12 13 6 3 Thuận thế 0 0 1 0 1 5 2 0 1 5 9 9 10 4 2 Hoán vị sinh ra thuận thế 11 9 10 4 5 15 7 1 2 8 14 12 13 6 3 Hoán vị 11 2 9 10 5 6 8 16 7 3 12 18 13 14 4 19 17 15 1 20 Thuận thế 0 0 1 0 1 5 2 0 1 5 9 9 10 4 2 Hoán vị sinh ra thuận thế 11 2 9 10 5 6 8 16 7 3 12 18 13 14 4 19 17 15 1 20 Nếu chỉ đúng 1 câu a hoặc b thì cho ½ số điểm của test tương ứng Bài 2: (10 điểm) Chấm theo bộ test gồm : 6 test Test 1: 1 điểm Test 2: 1 điểm Test 3: 2 điểm Test 4: 2 điểm Test 5 2 điểm Test 6 2 điểm Test 1 Test 2 Test 3 letters.inp letters.inp letters.inp 24 36 55 CAAB HFDFFB IEFCJ 3/2
ADCB AJHGDH FHFKC DGAGEH FFALF HFGCF HMCHH letters.out letters.out letters.out 3 6 10 Test 4 Test 5 Test 6 letters.inp letters.inp letters.inp 10 1 89 3 20 D QDTCYRNEF LMLINHDKMALNNLBCACLA A MFKGIJAXZ AGEHCEDKOGNIBFHFNHLI C XAGVNZYGR HCJBIGKBJBELCHCJCLOF B PPYUUPFKG B JEQVKFEWU E HCBRUZQPJ B YOVJVILYU A INXATSXKE B F letters.out letters.out letters.out 4 24 14 4/2