Đề thi Olympic Tin học sinh viên lần thứ XV khối Đồng đội chuyên (Năm 2006)

Chia sẻ: Tư Khấu Quân Tường | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

7
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề thi Olympic Tin học sinh viên lần thứ XV khối Đồng đội chuyên (Năm 2006) cung cấp cho thí sinh các bài tập giải quyết vấn đề lập trình gồm: tính điểm; biến đổi bảng số; rút gọn; những chiếc cọc; điểm nguyên; phân nhóm;... Mời các bạn cùng tham khảo chi tiết nội dung đề thi!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề thi Olympic Tin học sinh viên lần thứ XV khối Đồng đội chuyên (Năm 2006)

OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XV, 2006 Khối thi: Đồng đội chuyên Thời gian làm bài: 180 phút Ngày thi: 07-05-2006 Nơi thi: TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Tªn file Tªn file H¹n chÕ thêi Tªn bµi ch-¬ng tr×nh d÷ liÖu gian Tính điểm SCORE.* SCORE.INP 2s Biến đổi bảng số TABLE.* TABLE.INP 5s Rút gọn LIST.* LIST.INP 2s Những chiếc cọc STICKS.* STICKS.INP 2s Điểm nguyên POINTS.* POINTS.INP 5s Phân nhóm HQL.* HQL.INP 5s Nép ch-¬ng tr×nh nguồn. KÕt qu¶ xuÊt ra luång output chuÈn (mµn h×nh). Ngoµi kÕt qu¶ thÝ sinh kh«ng ®-îc ghi bÊt cø th«ng tin thªm. H·y lËp tr×nh gi¶i c¸c bµi sau ®©y: Bài 1: TÍNH ĐIỂM Tên chương trình: SCORE.* Trong kỳ thi vấn đáp học sinh phải trả lời các câu hỏi của thầy giáo. Nếu trả lời đúng, thầy giáo đánh dấu bằng ký tự ‘C’ (Correct), nếu sai thì đánh dấu ‘N’ (No Correct). Khi học sinh trả lời đúng, thầy sẽ đưa ra câu hỏi tiếp theo khó hơn câu trước, còn khi trả lời sai thầy sẽ cho câu hỏi mới dễ hơn. Sau khi thi xong, kết quả của mỗi học sinh là một xâu các ký tự ‘C’ và ‘N’. Điểm số của học sinh sẽ được tính như sau: Với các câu trả lời sai học sinh không được điểm, với mỗi câu trả lời đúng học sinh nhận được điểm bằng số lần trả lời đúng liên tiếp từ câu trả lời này trở về trước. Ví dụ, nếu kết quả là ‘CCNNCNNCCC’, thì điểm số sẽ là 1+2+0+1+0+0+1+2+3 = 10. Yêu cầu: Cho xâu kết quả độ dài không quá 1000, hãy tính điểm của học sinh. Dữ liệu: Vào từ file văn bản SCORE.INP: • Dòng đầu tiên chứa số nguyên T - số lượng Tests, • Mỗi dòng trong T dòng sau chứa một xâu kết quả thi. Kết quả: Đưa ra luồng output chuẩn, gồm T dòng, dòng thứ i chứa kết quả tương ứng với Tests thứ i (1iT). Ví dụ: SCORE.INP Kết quả 5 10 CCNNCNNCCC 9 CCNNCCNNCC 7 CNCNCNCNCNCNCN 55 CCCCCCCCCC 30 CCCCNCCCCNCCCCN Trang 1/4
Bài 2: BIẾN ĐỔI BẢNG SỐ Tên chương trình: TABLE.* Cho một lưới ô vuông gồm n dòng và n cột. Các dòng được đánh số từ 1 đến n từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải. Ô nằm ở vị trí dòng i và cột j của lưới được gọi là ô (i,j). Trên lưới đã cho, khoảng cách từ ô (i,j) tới ô (p,q) được tính bằng: i- p+j-q.Tại ô (i,j) của lưới ghi số nguyên không âm aij, i = 1, 2,..., n ; j = 1, 2,..., n. Với mỗi ô (i,j) gọi sij là khoảng cách ngắn nhất từ ô (i,j) đến một ô khác 0 . Một ô (i,j) chứa số 0 được gọi là ô thay thế nếu tồn tại duy nhất 1 ô (p,q) thoả: ➢ apq > 0, ➢ Khoảng cách từ ô (i, j) tới ô (p, q) bằng sij. Yêu cầu: Tính số lượng ô thay thế trên lưới. Dữ liệu : Vào từ file văn bản TABLE.INP, gồm nhiều Tests: • Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤ 10), • Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, trong mỗi nhóm: o Dòng đầu tiên ghi số nguyên dương n (n200). o Dòng thứ i trong số n dòng tiếp theo ghi n số nguyên dương ai1, ai2,..., ain là các số trên dòng thứ i của lưới, i = 1, 2,..., n; aij1000000. Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi một dấu cách. Kết quả: Đưa ra luồng output chuẩn, gồm T dòng, dòng thứ i chứa kết quả tương ứng với Tests thứ i (1iT). Ví dụ: TABLE.INP Kết quả 1 4 3 0 0 0 1 0 2 0 0 0 Bài 3: RÚT GỌN Tên chương trình: LIST.* Cho một dãy A gồm N số nguyên. Dãy A có thể được biểu diễn dưới dạng một xâu S theo các quy tắc sau: • Loại bỏ các phần tử trùng nhau trong dãy chỉ giữ lại một phần tử đại diện, • Các số còn lại được sắp xếp theo thứ tự tăng dần, • Lần lượt liệt kê các số tách nhau bởi dấu phẩy và một dấu cách sau dấu phẩy. • Dãy các số nguyên liên tiếp từ a tới b (a
o Dòng thứ 2 chứa n số nguyên, các số không nhất thiết phải khác nhau và có giá trị tuyệt đối không vượt quá 2*109. Hai số liên tiếp trên cùng một dòng được ghi cách bởi ít nhất một dấu cách. Kết quả: Đưa ra luồng output chuẩn, gồm T dòng, mỗi dòng chứa kết quả biểu diễn rút gọn. Dòng thứ i chứa kết quả tương ứng với Tests thứ i (1i T). Ví dụ: LIST.INP Kết quả 2 -1, 1, 3,..., 6 7 -10, 1,..., 14 1 3 5 -1 3 4 6 16 1 3 5 -10 3 4 6 2 7 10 9 8 11 13 12 14 Bài 4: NHỮNG CHIẾC CỌC Tên chương trình: STICKS.* Để dựng lều cho các đội tuyển tham dự kỳ thi Đồng đội, Ban tổ chức Olimpic Sinh viên mua N cây tre được đánh số từ 1 tới N với độ dài tương ứng là: h1, h2,..., hN. Qua việc đăng ký dự thi của các đội Ban tổ chức nhận thấy để làm đủ cho mỗi đội một lều cần phải có K cọc với độ dài bằng nhau và để tiện cho việc cưa độ dài của cọc là số nguyên. Mỗi chiếc cọc được cắt ra từ một cây nào đó và không được phép nối từ một số đoạn. Để các lều được thoáng mát Ban tổ chức mong muốn độ dài của cọc là lớn nhất. Yêu cầu: Cho N, h1, h2,..., hN và K. Hãy tìm độ dài nguyên d lớn nhất của cọc. Dữ liệu : Vào từ file văn bản STICKS.INP, gồm nhiều Test: • Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤10), • Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, với mỗi nhóm: o Dòng đầu chứa 2 số nguyên dương N và K (1N ≤10000, 1K ≤ 10000), o Dòng thứ 2 ghi N số nguyên h1, h2,..., hN (0
Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi một khoảng trắng. Kết quả: Đưa ra luồng output chuẩn, gồm T dòng, dòng thứ i chứa kết quả tương ứng với Tests thứ i (1i T). Ví dụ: POINT.INP Kết quả 1 18 6 -1 1 2 8 8 8 12 4 10 -2 7 -3 Bài 6. PHÂN NHÓM Tên chương trình: HQL.* Trên hành tinh Delta có N quốc gia. Các quốc gia được đánh số từ 1 tới N. Mỗi quốc gia đều còn có một số vấn đề bất đồng với không quá 3 quốc gia khác. Để duy trì sự cân bằng, hoà bình trong hành tinh, người ta thành lập một tổ chức với tên gọi là Hội quốc liên. Sắp tới sẽ diễn ra một kỳ họp Đại hội đồng của tổ chức này. Vì số lượng Quốc gia quá nhiều nên Ban tổ chức Đại hội muốn phân các quốc gia này thành hai nhóm để họp vào hai thời điểm khác nhau sao cho trong mỗi nhóm mỗi quốc gia có không quá 1 quốc gia bất đồng với mình. Yêu cầu: Hãy giúp Ban tổ chức phân các Quốc gia thành hai nhóm thỏa mãn yêu cầu trên. Dữ liệu : Vào từ file văn bản HQL.INP, gồm nhiều Tests: • Dòng đầu tiên chứa số nguyên T - số lượng Tests (1 ≤ T ≤ 10), • Tiếp theo là T nhóm dòng đưa ra thông tin về các Tests, với mỗi nhóm dòng: o Dòng đầu chứa số N là số lượng quốc gia trên hành tinh Delta (1N8000). o Dòng thứ i trong N dòng tiếp theo chứa các không quá 4 số: số đầu là số lượng các quốc gia có bất đồng với quốc gia thứ i, tiếp theo là chỉ số của các quốc gia đó. Nếu quốc gia thứ i không bất đồng với bất kỳ một quốc gia nào thì dòng thứ i chứa duy nhất một số 0. Kết quả: Ghi ra luồng output chuẩn kết quả của T Tests, với mỗi một nhóm dòng: Số -1 nếu không tồn tại phương án phân thành hai nhóm. Trong trường hợp có phương án phân nhóm hãy ghi ra hai dòng: • Dòng đầu chứa chỉ số các quốc gia trong nhóm thứ nhất. • Dòng thứ 2 chứa chỉ số các quốc gia thuộc nhóm thứ 2. Hai số liên tiếp trên cùng một dòng được ghi cách bởi ít nhất một dấu cách. Ví dụ: HQL.INP Kết quả 1 1 4 6 7 7 2 3 5 3 2 3 4 3 1 3 6 2 1 2 2 1 5 1 4 1 2 0 Trang 4/4