Kỳ thi chọn đội tuyển dự thi học sinh giỏi quốc gia lớp 12 THPT năm học 2012 - 2013 môn thi Tin Học

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ TĨNH ĐỀ CHÍNH THỨC - VÒNG 1 (Đề thi có 2 trang) KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HỌC SINH GIỎI QUỐC GIA LỚP 12 THPT NĂM HỌC 2012 - 2013 Môn thi Tin học Thời gian 180 phút (Không kể thời gian giao đề) TỔNG QUAN BÀI THI Tên bài Tệp chương trình Tệp dữ liệu vào Tệp dữ liệu ra Bài 1 Thời gian làm việc của máy tính THOIGIAN.PAS THOIGIAN.INP THOIGIAN.OUT Bài 2 Số duy nhất SOLIEU.PAS SOLIEU.INP Bài 3 Máy đổi thẻ tự động THE.PAS THE.INP THE.OUT Sử dụng ngôn ngữ lập trình Pascal hãy lập chương trình giải các bài toán sau đây: Bài 1. Thời gian làm việc của máy tính N máy tính có số hiệu 1,..,N thực hiện N chương trình. Thời gian thực hiện chương trình của máy tính có số hiệu i là từ thời điểm thời gian ai đến thời điểm thời gian bi (1< N £ 1000; ai, bi nguyên dương, ai<bi£2000). Hãy xác định nhiều nhất các khoảng thời gian thực hiện chương trình của các máy tính sao cho không có thời điểm thời gian nào trùng nhau. Mỗi khoảng thời gian tìm được là chỉ bao gồm các thời điểm thời gian thực hiện chương trình của một máy tính. Dữ liệu vào là tệp văn bản THOIGIAN.INP có cấu trúc: Dòng đầu tiên ghi số N; N dòng tiếp theo, mỗi dòng ghi thời điểm thời gian bắt đầu và thời điểm thời gian kết thúc việc thực hiện chương trình của một máy tính (ghi cách nhau ít nhất là một ký tự trống). Thông tin về khoảng thời gian thực hiện chương trình của các máy tính được ghi tuần tự theo thứ tự tăng dần của số hiệu của các máy tính đó. Dữ liệu ra là tệp văn bản THOIGIAN.OUT có cấu trúc: Dòng đầu tiên ghi số lượng các khoảng thời gian tìm được; Các dòng tiếp theo, ghi số hiệu của các máy tính có các khoảng thời gian tìm được. Mỗi số hiệu ghi trên một dòng và số hiệu của máy tính nào có khoảng thời gian với các thời điểm thời gian bắt đầu, thời điểm thời gian kết thúc chương trình nhỏ hơn thì được ghi trước. Ví dụ: Tệp THOIGIAN.INP Tệp THOIGIAN.OUT 8 2 3 4 5 10 12 13 15 1 9 2 5 6 8 7 15 5 1 2 7 3 4 Bài 2. Số duy nhất Bộ số liệu của một đề tài nghiên cứu khoa học được lưu giữ trong tệp văn bản SOLIEU.INP, mỗi số chiếm một dòng dài không quá 20 chữ số. Do đặc thù của đề tài mà bộ số liệu này có đặc điểm là chỉ có duy nhất một số xuất hiện đúng một lần, các số còn lại đều xuất hiện đúng N lần (N là một số chẵn khác 0). Để phục vụ cho việc nghiên cứu đề tài đòi hỏi phải tìm cho được số xuất hiện đúng một lần trong bộ số liệu đó. Hãy giúp các nhà khoa học giải quyết vấn đề đã nêu. Dữ liệu vào là tệp văn bản SOLIEU.INP. Dữ liệu ra kết xuất trên màn hình. Ví dụ: Tệp SOLIEU.INP Dữ liệu ra 1234 231 1234 231 49 528 49 528 Bài 3. Máy đổi thẻ tự động Có một máy giải trí tự động có M cửa dùng để đổi thẻ. Có các thẻ mã số từ 1,..,N. Nếu ta bỏ thẻ có mã số i vào một cửa nào đó thì máy sẽ thu thẻ đó và cho ra một thẻ có mã số nào đó trong khoảng 1..N. Máy đổi thẻ hoạt động theo thông tin ghi trong tệp văn bản THE.INP: - Dòng đầu tiên ghi các số N, M, x, y (1£ M, N £ 200, 1£ x,y £ N); - N dòng tiếp theo, mỗi dòng chứa M số tạo thành một bảng có kích thước N x M. Phần tử nằm trên dòng i, cột j của bảng này cho biết nếu ta bỏ thẻ có số hiệu i vào cửa j thì sẽ thu được thẻ có số hiệu chính là giá trị của phần tử đó; - Các số trên mỗi dòng của tệp ghi cách nhau ít nhất là một ký tự trống. Với mỗi cặp thẻ có số hiệu x và y cho trước (xy), hãy cho biết có cách nào nhanh nhất để dùng thẻ có số hiệu x thu được thẻ có số hiệu y hay không? Dữ liệu ra là tệp văn bản THE.OUT trình bày theo dạng: Bỏ thẻ x vào cửa ... thu được thẻ ... ......... Bỏ thẻ ... vào cửa ... thu được thẻ y Nếu không tìm được cách để từ thẻ có số hiệu x thu được thẻ có số hiệu y thì ghi vào tệp thông báo ‘Tu the x khong thu duoc the y’. Ví dụ: Tệp THE.INP Tệp THE.OUT Tệp THE.INP Tệp THE.OUT 5 4 2 1 2 3 5 1 3 4 4 3 1 5 2 4 5 3 2 1 3 4 2 4 Bo the 2 vao cua 1 thu duoc the 3 Bo the 3 vao cua 1 thu duoc the 1 5 4 4 5 2 2 2 4 1 4 4 4 1 5 2 4 1 1 2 2 3 4 2 4 Tu the 4 khong thu duoc the 5 ------------------------------ 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. Họ và tên thí sinh: Số báo danh: ..