đề thi học sinh giỏi môn tin học lớp 12 tỉnh gia lai năm 2013 - 2014 (đề số 2)

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN ĐỘI TUYỂN DỰ THI CẤP QUỐC GIAGIA LAI LỚP 12 THPT, NĂM HỌC 2013 2014Môn: TIN HỌCĐỀ DỰ BỊ Thời gian làm bài: 180 phút (không kể thời gian phát đề)Ngày thi: 27/9/2013(Đề thi gồm trang, 03 bài)Bài 1. (6 điểm) Dãy con không tăng dài nhất Cho dãy số nguyên dương có phần tử a1 a2 …, an Tìm dãy con có các phần tử liêntiếp giảm dần (ai ai+1 i=1..n-1) dài nhất của dãy A, thỏa mãn giá trị trung bình cộng của cácphần tử trong dãy con đó lớn hơn hoặc bằng giá trị nguyên dương k. Nếu có nhiều dãy thỏađiều kiện có độ dài bằng nhau thì chọn dãy có trung bình cộng lớn nhất. Yêu cầu: Cho dãy A, hãy xác định số phần tử của dãy con không tăng dài nhất và vị trí đầu, vịtrí cuối của dãy con đó trong dãy A.Dữ liệu vào: Cho từ tệp văn bản DAYCON.INP gồm: Dòng đầu ghi số hai số nguyên và (1 n, 100000). Dòng tiếp theo lần lượt ghi các số nguyên a1 a2 …, an (0 ai 10000 với i=1..n). Cácsố trên cùng một dòng ghi cách nhau ít nhất một dấu cách. Dữ liệu ra: Ghi ra tệp văn bản DAYCON.OUT gồm: Dòng đầu tiên: Độ dài của dãy con tìm được. Trường hợp không tìm được dãy con thỏamãn điều kiện thì ghi số 0. Dòng thứ hai: Vị trí bắt đầu và kết thúc của dãy con đó, hai số cách nhau ít nhất một dấucách.Ví dụ: DAYCON.INP DAYCON.OUT12 45 44 Bài 2. (7 điểm) Đếm số hình chữ nhật trên lướiTrên một tờ giấy kẻ vuông, kích thước người ta tạo ra một số hình chữ nhật bằng cáchđịnh vị một số liên tiếp kề nhau, các hình chữ nhật này từng đôi một không giao nhau, khôngliền kề theo phép kề đỉnh. Cho bảng (N N), giá trị phần tử của bảng được xác định như sau: A[i,j] nếu tương ứng trên tờ giấy thuộc một hình chữ nhật nào đấy. A[i,j] nếu tương ứng trên tờ giấy không thuộc một hình chữ nhật nào cả. Hãy tìm số lượng các hình chữ nhật và các tọa độ đỉnh trái trên, phải dưới của mỗi hình chữnhật trong bảng, một hình chữ nhật tối thiểu trở lên. Dữ liệu vào Cho trong tệp văn bản HCN.INP dòng đầu ghi số N. dòng tiếp theo mỗidòng là xâu nhị phân độ dài N, giá trị nếu tương ứng thuộc một hình chữ nhật, giá trị nếuô tương ứng không thuộc một hình chữ nhật nào cả.Trang 2Dữ liệu ra Ghi ra tệp văn bản HCN.OUT theo cấu trúc: Dòng đầu ghi số là số hình chữ nhật có trong bảng. dòng tiếp theo mỗi dòng ghi số p, q, r, với nghĩa: cặp số p, là tọa độ đỉnh tráitrên, cặp số r, là tọa độ đỉnh phải dưới của một hình chữ nhật trong hình chữ nhật cótrên bảng.Ví dụ:BÀI 3. (7 điểm) Vòng số nguyên tố Một vòng tròn chứa 2n vòng tròn nhỏ (Xem hình vẽ). Các vòng tròn nhỏ được đánh số từ đến2n theo chiều kim đồng hồ. Cần điền các số tự nhiên từ đến 2n mỗi số vào một vòng tròn nhỏsao cho tổng của hai số trên hai vòng tròn nhỏ liên tiếp là số nguyên tố. Số điền vòng trònnhỏ luôn là số 1. Dữ liệu vào Cho trong tệp văn bản VONG.INP chứa số nguyên dương (1 10) Dữ liệu ra Ghi ra tệp văn bản VONG.OUT: Dòng đầu tiên ghi số lượng các cách điền số tìm được (k). Dòng thứ trong số dòng tiếp theo ghi các số trong các vòng tròn nhỏbắt đầu từ vòng tròn nhỏ đọc theo thứ tự của các vòng tròn nhỏ Ví dụ:----------------Hết---------------- 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.Trang 2HCN.OUT51 31 73 44 76 4VONG.OUT2 61 4Trên đây chỉ là phần trích dẫn 10 trang đầu của tài liệu và có thế hiển thị lỗi font, bạn muốn xem đầyđủ tài liệu gốc thì ấn vào nút Tải về phía dưới.