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

Tham khảo tài liệu đề thi olympic tin học sinh viên lần thứ 16, 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ứ 16 OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XVI, 2007 Khối thi: Cá nhân Cao đẳng Thời gian làm bài: 180 phút Ngày thi: 10/11/2007 N¬i t hi: §¹i häc §µ N½NGTên bài File nguồn nộp File dữ liệu File kết quả Thời gian mỗi testTính lương LUONG.XLSXâu lặp WLOOP.* WLOOP.INP WLOOP.OUT 1 giâyNhật kí hành trình TRACE.* TRACE.INP TRACE.OUT 1 giâyChú ý: Dấu * được thay thế bởi đuôi ngầm định của ngôn ngữ được sử dụng để cài chương trình; Thí sinh phải nộp cả file mã nguồn của chương trình và file chương trình thực hiện (chương trình đã được biên dịch ra file .exe).Bài 1. Tính lươngNăm 2007, lương tháng của nhân viên Công ty Tình Nguyện được tính dựa trên số nămcông tác, mức lương chính và xếp loại lao động. - Số năm công tác được tính bằng cách lấy phần nguyên của tổng số ngày đã công tác từ ngày vào công ty cho đến ngày hôm nay (ngày 10 tháng 11 năm 2007) chia cho 365; - Có 4 mức lao động được xếp loại: 1/2/3/4, ứng với mỗi mức có một số tiền thưởng, phạt tương ứng là 500000, 200000, 0, - 100000. - Lương thực tế của nhân viên là tổng của lương chính, phụ cấp (3% lương chính nhân với số năm công tác) và số tiền thưởng phạt. Hãy sử dụng MS Excel tạo tệp LUONG.XLS để giải quyết một số việc về tính lươngcho Công ty Tình Nguyện, có 100 nhân viên. Giả sử trên Sheet 1 dữ liệu sẽ được nhập vào các ô Ak, Bk, Ck tương ứng là ngày vàocông ty, mức xếp loại lao động (1, 2, 3, hoặc 4) và lương chính (không quá mười triệu) củacác nhân viên, với k = 1, ..., 100. Lập các công thức để tính tiền thưởng trung bình của cácnhân viên xếp loại 1 và 2 trong tháng, và tổng tiền lương thực tế mà công ty phải trả trongtháng cho toàn bộ nhân viên; và kết xuất tương ứng vào ô G1 và H1 của Sheet 1. Chẳng hạn, với số nhân viên là 5 ta có bảng mẫu sau: A B C D E F G H 1 01/10/1971 1 10000000 300000.00 41355120.73 2 13/03/2001 2 2366669 3 06/10/2007 4 540000 4 11/12/2005 3 9136044 5 19/10/1999 2 5655102 Trang 1/3 Chú ý rằng bạn phải định dạng kiểu dữ liệu cho các ô ở cột A là Date/Custom (khuôndạng dd/mm/yyyy, ví dụ: 20/11/2007); cột B và C là Number không có số thập phân vàkhông có dấu tách nhóm số (ví dụ: 6668); ô G1 và H1 là Number với 2 chữ số sau dấuchấm thập phân và không có dấu tách nhóm số (ví dụ: 12345.68). Bạn có thể sử dụng các ô ngoài 2 ô G1, H1 và các ô Ak, Bk, Ck, với k = 1, ..., 100 đểtạo các công thức trung gian. Ghi chú: Bài này sẽ được chấm bằng cách nhập dữ liệu của các test khác nhau vàocác ô Ak, Bk, Ck, với k = 1, ..., 100 và sau đó kiểm tra kết quả ở các ô G1 và H1 trongSheet 1 của tệp LUONG.XLS mà thí sinh nộp.Bài 2. Xâu lặpTrong giờ thực hành soạn thảo văn bản trên MS Word, mỗi sinh viên cần gõ một xâu kí tựbất kì. Khi xem xét xâu kết quả của sinh viên, giáo viên phát hiện ra rằng có một số xâu lặpđặc biệt được tạo thành bằng cách ghép k lần một xâu con (k > 1). Ví dụ, ’ABABAB’ làmột xâu đặc biệt, lặp lại 3 lần xâu con ’AB’. Hãy lập trình giúp giáo viên tìm số các xâu lặp trong số N xâu mà các sinh viên đã gõ,biết rằng các xâu này khác rỗng, đôi một khác nhau và độ dài của mỗi xâu không quá 255. Dữ liệu: vào từ file văn bản WLOOP.INP có cấu trúc như sau: - Dòng đầu tiên chứa số nguyên dương N, với N ≤ 1000; - Dòng thứ i trong N dòng tiếp theo chứa một xâu mà sinh viên thứ i đã gõ, với i = 1, ..., N. Kết quả: ghi ra file văn bản WLOOP.OUT gồm một số nguyên không âm là số lượngxâu lặp tìm được. Ví dụ: WLOOP.INP WLOOP.OUT 4 1 Welcom!welcom! Welcom!Welcom! VOI2007&ACM/ICPC DANANG, 9-11/2007Bài 3. Nhật kí hành trìnhĐoàn thám hiểm sa mạc Gô bi xuất phát từ điểm có tọa độ (XS,YS) sau N ngày khảo sát samạc đã hoàn thành xuất sắc các nhiệm vụ đề ra và về tới đích an toàn ở điểm có tọa độ(XD,YD). Đầu mỗi ngày trong cuộc hành trình, khi mặt trời còn chưa kịp tỏa ánh nắng chóichang như muốn thiêu đốt mọi sinh vật trên sa mạc, đoàn thám hiểm di chuyển tới điểmkhảo sát mới, cách điểm hiện tại một đơn vị độ dài và đi theo một trong số 4 hướng: Đông(E), Bắc (N), Tây (W) hoặc Nam (S). Như vậy, nếu ban đầu trước khi lên đường vị trí củađoàn ở tọa độ (X, Y) thì vị trí mới nơi đoàn thực hiện các khảo sát và ngủ qua đêm sẽ lànhư sau: Hướng đi Tọa độ X mới Tọa độ Y mới X+1 Y E X Y+1 N X-1 Y W X Y-1 S Trang 2/3 Đường đi được ghi lại trong nhật kí công tác dưới dạng xâu kí tự T chỉ chứa các kí tựthuộc tập {E, N, W, S}. Ví dụ, từ điểm xuất phát XS = 1, YS = 2, với hành trình T = ’ENWNEEESESWWSW’,điểm đích của chuyến khảo sát sẽ là XD = 2, YD = 1. Tùy theo yêu cầu thực tế, một điểm có thể được quay lại khảo sát nhiều lần. Mọi việc dường như vô cùng tốt đẹp nếu như không có một sự cố nhỏ: báo cáo côngtác (in trên máy vi tính) bị trả về để bổ sung chỉnh lý vì trong xâu T xác định hành trình có2 kí tự lạ liền nhau không chỉ hướng đi, tức ...