Đề thi olympic tin học sinh viên lần thứ 19

Tham khảo tài liệu đề thi olympic tin học sinh viên lần thứ 19, công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Đề thi olympic tin học sinh viên lần thứ 19 OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XIV, 2005 Khối thi: Cá nhân không Chuyên Tin học Thời gian làm bài: 165 phút Ngày thi: 23-04-2005 Nơi thi: TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH Tên tập file Hạn chế Tên bài Tên file dữ liệu Tên file kết quả chương trình thời gian Thám hiểm EXPLORE.??? EXPLORE.INP EXPLORE.OUT 1 giây Tìm đặc trưng ảnh FEATURE.??? FEATURE.INP FEATURE.OUT 1 giây (Phần mở rộng tên tập tin chương trình ??? là PAS hoặc CPP)Bài 1. Thám hiểmĐoàn thám hiểm Nam cực xuất phát từ Trạm nghiên cứu đặt ở điểm có toạ độ (0, 0). Trục OXchạy từ tây sang đông, trục OY chạy từ nam lên bắc. Ban đầu Đoàn đi theo một trong số 4hướng Đông (E), Tây (W), Nam (S) hoặc Bắc (N). Sau khi đi một quảng đường là một đơn vịđộ dài Đoàn dừng lại thực hiện các đo đạc khảo sát cần thiết và tuỳ theo tình hình thực tế,trưởng đoàn sẽ quyết định đi tiếp theo Yhướng nào. Để đánh dấu các điểm trênbản đồ khai thác và dễ dàng xác định Nđường trở về lịch trình di chuyển trong 4nhật ký được ghi dưới dạng xâu các ký W Etự trong tập {E, W, S, N}. Tuy vậy thờitiết ở địa cực nổi tiếng là đỏng đảnh. 2 SBão tuyết có thể nổi lên bất kỳ lúc nào E Ckèm theo các cơn bão từ làm rối loạn la R Sbàn. Khi đó đường đi sẽ được ghi nhận X -4 -2 2 4bằng các ký tự L - Rẽ trái, R - Rẽ phải, B W0 S N– Đi ngược lại hướng vừa đi hoặc C - CTiếp tục đi thẳng theo hướng cũ. Mỗi khi R -2bão từ chấm dứt, la bàn hoạt động bình W W C Rthường trở lại lịch trình di chuyển lạiđược ghi nhận bằng các ký tự E, W, S,N. Ở thời điểm ban đầu của cuộc thámhiểm thời tiết tốt, không có bão từ. Trong suốt cuộc hành trình có thể không có trận bão từnào hoặc bão từ có thể xẩy ra nhiều lần. Ví dụ, lịch trình ở hình bên có thể được ghi nhậnbằng xâu WRECSSCRWWCRN.Yêu cầu: Cho một lịch trình di chuyển xác định bởi xâu Z độ dài không quá 200 gồm các kýtự trong tập {E, W, S, N, L ,R, B, C}, bắt đầu bằng một trong số 4 ký tự đầu tiên. Hãy tínhkhoảng cách theo đường chim bay từ điểm dừng cuối của đoàn thám hiểm tớỉ Trạm nghiêncứu mà Đoàn xuất phát.Olympic Tin học Sinh viên Việt Nam lần thứ 14, 2005 – Khối không Chuyên tin họcKhoảng cách d theo đường chim bay giữa hai điểm có toạ độ (X1, Y1) và (X2,Y2) được tính ( X 1 − X 2 ) 2 + (Y1 − Y2 ) 2 .theo công thức d =Dữ liệu: Vào từ file văn bản EXPLORE.INP gồm một dòng chứa xâu Z xác định một lịchtrình di chuyển của đoàn thám hiểm.Kết quả: Đưa ra file văn bản EXPLORE.OUT một số thực có 3 chữ số sau dấu chấm thậpphân, đó là khoảng cách tìm được với dữ liệu vào đã cho.Ví dụ: EXPLORE.INP EXPLORE.OUT WNRN 2.000 EXPLORE.INP EXPLORE.OUT WRECSSCRWWCRN 3.000Bài 2. Tìm đặc trưng ảnhMột nhóm nghiên cứu xử lý ảnh của trường ĐH Khoa học tự nhiên, ĐHQG Tp.HCM đanggiải quyết bài toán nhận dạng mặt người trong ảnh. Ảnh chụp mặt người sau khi đã xử lý làmột bảng vuông A kích thước N x N (10 ≤ N ≤ 800) với mỗi ô (I,J) (1 ≤ I, J ≤ N) có giá trị từ0 đến 255 là mức xám của ảnh tại ô này (trong đó 0 là màu nền). Để xác định vị trí có thể làmặt người, nhóm cần thống kê các đặc trưng có dạng hình vuông kích thước K x K (1 ≤ K ≤40) trong đó tất các các giá trị trong hình vuông đều phải khác 0.Yêu cầu : Từ một ảnh chụp mặt người, hãy giúp nhóm nghiên cứu đếm tất cả các đặc trưngcó trong ảnh đó.Dữ liệu : Vào từ file văn bản FEATURE.INP trong đó : • Dòng đầu chứa hai sô N và K • Dòng thứ I trong N dòng tiếp theo chứa tương ứng dòng thứ I của bảng A.Các số ghi trên một dòng được ghi cách nhau bởi ít nhất một khoảng trắng. Mỗi dòng có N sốnguyên. Dòng thứ I là các giá trị của N phần tử trong dòng thứ I-1 trong bảng vuông AKết quả : Ghi ra file văn bản FEATURE.OUT số lượng đặc trưng tìm được.Ví dụ: FEATURE.INP FEATURE.OUT 62 7 0 12 15 0 33 30 17 19 23 15 16 0 11 12 0 14 14 0 0 10 11 8 10 0 0 8 7 12 0 0 0 0 11 13 0 0 2Olympic Tin học Sinh viên Việt Nam lần thứ 14, 2005 – Khối không Chuyên tin học ĐỀ THI TRẮC NGHIỆM - KHỐI KHÔNG CHUYÊN Thời gian làm bài: 15 phút1. Cho hai số nhị phân A = 11001101 và B = 1010010. Hãy cho biết giá trị kết quả của phéptrừ A - B trong hệ nhị phân:A. 1100110 B. 1111011C. 1010101 ...