Kỳ thi học sinh giỏi thành phố - Năm học 2000-2001 môn : tin học trung học cơ sở (thời gian : 150 phút – không kể phát đề)

KỲ THI HỌC SINH GIỎI THÀNH PHỐ - NĂM HỌC 2000-2001 ĐỀ CHÍNH THỨC Môn : TIN HỌC TRUNG HỌC CƠ SỞ (Thời gian : 150 phút – không kể phát đề) BÀI 1 : BÀI TOÁN MA TRẬN Người ta tạo một ma trận số nguyên 3 x 3 ( bảng số gồm 3 dòng và 3 cột), sau đó sắp xếp lại ma trận theo một số phép biến đổi ma trận cho trước. Các số hạng của ma trận hình thành từ trái sang phải, từ trên xuống dưới lần lượt từ số các số 1, 2, 3, 4, 5, 6, 7, 8, 9 xuất hiện trong dãy số un cho trước (xem ví dụ). Các phép biến đổi ma trận qui ước như sau: Phép biến đổi 1 : Thay các số hạng của hàng 2 bằng số hạng của hàng 2 cộng 2 lần số hạng cùng cột của hàng 1 Phép biến đổi 2 : Thay các số hạng của hàng 3 bằng số hạng của hàng 3 cộng 2 lần số hạng cùng cột của hàng 2 Phép biến đổi 3 : Thay các số hạng của cột 2 bằng số hạng của cột 2 cộng 2 lần số hạng cùng hàng của cột 1 Phép biến đổi 4 : Thay các số hạng của cột 3 bằng số hạng của cột 3 cộng 2 lần số hạng cùng hàng của cột 2 Ví dụ : Xem ma trận ở giữa và các phép biến đổi ma trận tương ứng: 1 2 P2 P1 1 2 3 6 9 12 7 8 9 3 4 5 6 15 18 1 2 3 4 5 6 7 8 9 21 1 2 7 4 5 16 7 8 25 P4 1 4 3 4 13 6 7 22 9 P3 Hãy lập trình để tạo ma trận ban đầu và tìm ma trận kết quả cuối cùng sau khi thực hiện lần lượt các phép biến đổi. Phép biến đổi sau thực hiện trên ma trận kết quả của phép biến đổi trước đó. Dữ liệu vào : Dữ liệu vào được lưu trên tập tin văn bản MATRIX.IN (hoặc nhập từ bàn phím) gồm hai dòng : - Dòng đầu tiên ghi một số con số 1, 2, 3, 4 cách nhau một khoảng trắng. Mỗi số tương ứng một phép biến đổi ma trận; - Dòng tiếp theo ghi các số hạng của một dãy số un gồm nhiều số 1,2,3,4,5,6,7,8,9 ( không quá 1000 số ) cách nhau một khoảng trắng. Dữ liệu ra: Dữ liệu ra được lưu trên tập tin MATRIX.OUT (hoặc xuất ra màn hình) gồm 6 dòng ghi các số hạng của ma trận 3 x 3 ban đầu sau khi hình thành theo qui tắc trên và ma trận kết quả sau khi lần lượt duyệt qua hết tất cả các phép biến đổi ma trận . Ví dụ: MATRIX.IN ( hoặc nhập từ bàn phím) 1 2 4 3 1 9 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 4 4 4 4 4 6 6 6 6 6 6 6 5 5 5 5 5 5 3 3 3 3 2 2 2 1 1 ( trong dãy này có 2 số 1; 3 số 2; 4 số 3; 5 số 4; 6 số 5; 7 số 6; 8 số 7; 9 số 8; 1 số 9 ) 2 3 4 5 6 7 8 9 1 Kết quả MATRIX.OUT ( hoặc xuất ra màn hình ) 2 7 10 13 44 59 26 85 97 BÀI 2: BÀI TOÁN KHOẢNG CÁCH Giả sử có 2 điểm A(x1 ; y1 ) và B (x2 ; y2). Khoảng cách hai điểm A và B cho bởi công thức Cho tọa độ của n điểm trên mặt phẳng tọa độ. Người ta muốn biết những cặp điểm nào có khoảng cách lớn nhất. Nhiệm vụ Lập trình cho biết toạ độ những cặp điểm có khoảng cách lớn nhất và tính khoảng cách đó. Dữ liệu vào : Dữ liệu vào được lưu trên tập tin văn bản KHCACH.INP (hoặc nhập từ bàn phím) gồm nhiều dòng. + Dòng đầu tiên : số n ( n<100); + n dòng còn lại, mỗi dòng ghi hai số nguyên lần lượt ứng với hoành độ và tung độ của từng điểm. Dữ liệu ra : Dữ liệu ra được lưu trên tập tin văn bản KHCACH.OUT (hoặc xuất ra màn hình) gồm nhiều dòng : -         Dòng thứ nhất ghi khoảng cách lớn nhất ( làm tròn hai số lẻ thập phân ); -         Các dòng còn lại ghi toạ độ từng cặp điểm tương ứng. Ví dụ : KHCACH.INP( hoặc nhập từ bàn phím) 7 -5 -5 -2 -1 11 -1 12 -5 -5 3 -4 9 9 11 KHCACH.OUT ( hoặc xuất ra màn hình ) 21.26 -5 -5 9 11 -4 9 12 -5 Trong ví dụ này có hai cặp điểm (-5,-5) (9,11) và ( -4,9) (12, -5) có cùng koảng cách là 21.26 là khoảng cách lớn nhất giữa các cặp điểm trên. Yêu cầu kĩ thuật : Các bài làm của thí sinh lưu trên các tập tin có tên lần lược là Bai1.pas và Bai2.pas + Khuyến khích học sinh làm bài theo cách : dữ liệu vào và dữ liệu ra lưu trên các tập tin. HẾT ĐỀ THI CHÍNH THỨC KỲ THI HỌC SINH GIỎI THÀNH PHỐ - NĂM HỌC 2001-2002 Môn : TIN HỌC TRUNG HỌC CƠ SỞ (Thời gian : 150 phút – không kể phát đề) BÀI 1 : BÀI TOÁN PHỦ BÀN CỜ Cho một bàn cờ vuông n x n bị loại bỏ một ô ( i, j) . Người ta muốn phủ kín bàn cờ bằng các thanh chữ L, mỗi thanh đặt lên bàn cờ sẽ phủ được 3 ô vuông của bàn cờ ( xem hình vẽ) 1 1 2 2 1 0 4 2 3 4 4 5 3 3 5 5 Hãy lập trình cho biết có thể phủ kín được bàn cờ không và nếu được thì cho một phương án để phủ kín bàn cờ . Dữ liệu vào : Dữ liệu vào được lưu trên tập tin văn bản BANCO.IN gồm hai dòng : ·         Dòng đầu tiên ghi số n ·         Dòng thứ hai gồm 2 số chỉ vị trí hàng và cột của ô cần bỏ ra. Dữ liệu ra: Dữ liệu ra được xuất ra màn hình Hoặc : KHONG THE PHU KIN BAN CO (nấu không phủ kín được bàn cờ) Hoặc n dòng : mỗi dòng ghi chỉ số của các thanh chữ L phủ các ô trong dòng tương ứng của bàn cờ, trong đó ô bị loại được đánh số 0. Các số được ghi cách nhau một khoảng trắng. Ví dụ : BANCO.IN 4 2 2 Kết quả xuất ra màn hình 1 1 2 2 1 0 4 2 3 4 4 5 3 3 5 5 * Không kiểm tra dữ liệu vào BÀI 2: BÀI TOÁN KHOẢNG CÁCH Cho tọa độ của n điểm A1, A2, A3,. . . .An và điểm I trên mặt phẳng tọa độ. Người ta muốn biết khoảng cách từ I đến các đường thẳng A1 A2, A2A3,. . . .An-1An và so sánh các khoảng cách này. Nhiệm vụ Lập trình cho biết toạ : ·         Khoảng cách d1,d2,d3,dn từ I đến các đường thẳng A1 A2, A2A3,. . . .An-1An . ·          Giá trị lớn nhất của d1,d2,d3,dn ·          Giá trị nhỏ nhất của d1,d2,d3,dn Dữ liệu vào : Dữ liệu vào được lưu trên tập tin văn bản DIEM.INP gồm nhiều dòng. + Dòng đầu tiên : số n ( n<50); + n dòng còn lại, mỗi dòng ghi hai số nguyên lần lượt ứng với hoành độ và tung độ của lần lượt từng điểm A1, A2, A3,. . . .An. Dữ liệu ra : Dữ liệu ra được lưu trên tập tin văn bản DIEM.OUT gồm 3 dòng : ·         Dòng thứ nhất : ghi n khoảng cách d1,d2,d3,dn ( làm tròn hai số lẻ thập phân ); ·         Dòng thứ nhì : ghi khoảng cách lớn nhất ·         Dòng thứ ba : ghi khoảng cách nhỏ nhất Ví dụ : DIEM.INP 5 1.     6 3.     8 6.     8 8.     6 3.     4 DIEM.OUT 1.41 1.41 1.86 2.00 3.54 3.54 1.41 * Không kiểm tra dữ liệu vào Yêu cầu kĩ thuật : Các bài làm của thí sinh lưu trên các tập tin có tên lần lượt là Bai1.pas và Bai2.pas HẾT