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

Đề thi Olympic Tin học sinh viên lần thứ XV khối Đồng đội không 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; phân phòng ở; nhà hóa học; sơn hàng rào;... Mời các bạn cùng tham khảo chi tiết nội dung đề thi!
Nội dung trích xuất từ tài liệu:
Đề thi Olympic Tin học sinh viên lần thứ XV khối Đồng đội không chuyên (Năm 2006) OLYMPIC TIN HỌC SINH VIÊN LẦN THỨ XV, 2006 Khối thi: Đồng đội không 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ổng Tên file Tên file Tên file Hạn chế thời Tên bài điểm chương trình dữ liệu kết quả gian cho mỗi test cho bài Tính điểm SCORE.EXE SCORE.INP SCORE.OUT 2 giây 20Phân phòng ở ROOM.EXE ROOM.INP ROOM.OUT 5 giây 30 Nhà hóa học GOLD.EXE GOLD.INP GOLD.OUT 2 giây 30Sơn hàng rào PAINT.EXE PAINT.INP PAINT.OUT 2 giây 20Hãy lập trình giải các bài sau đây:Bài 1. Tính điểmTrong 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ầygiáo đánh dấu bằng ký tự ‘C’ (Correct), nếu sai thì đánh dấu ‘N’ (No Correct). Khi học sinhtrả 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ẽ chocâ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 chứa một xâu kết quả thi.Kết quả: Đưa ra file văn bản SCORE.OUT điểm số của kết quả thi.Ví dụ: SCORE.INP SCORE.OUT CCNNCNNCCC 10Bài 2. Phân phòng ởMột nhóm N nhà tỷ phú tổ chức đi đánh golf. Tại địa điểm đánh golf có một dãy các ngôi nhànghỉ nằm trên một địa thế sông núi rất hùng vĩ, có ngôi nhà thì cạnh sông, có ngôi nhà thìcạnh núi ... Mỗi ngôi nhà chỉ ở được một người. Đây cũng chính là lý do khiến các nhà tỷ phúkhông sao thỏa thuận được người nào sẽ ở ngôi nhà nào. Để giải quyết bế tắc và chiều lòng 1các tỷ phú, giám đốc khu nghỉ mát quyết định sử dụng M ngôi nhà liền nhau, đánh số từ 1đến M, để các nhà tỷ phú lấy ra N phòng trong đó. Nhà tỷ phú thứ i trong nhóm sẽ sử dụng sốchứng minh thư Si của mình (không có hai nhà tỷ phú nào có cùng số chứng minh thư) đểchọn ra được ngôi nhà mình sẽ ở. Thao tác chọn sẽ như sau: • Nhà tỷ phú đó sẽ bắt đầu đếm từ ngôi nhà đánh số 1, • Dừng lại ở ngôi nhà tương ứng với số chứng minh thư của mình, • Nếu đếm đến ngôi nhà đánh số M thì lại tiếp tục đếm từ ngôi nhà đánh số 1.Yêu cầu: Hãy giúp giám đốc khu nghỉ mát tìm ra số M bé nhất để không có hai nhà tỷ phúnào chọn cùng một ngôi nhà theo các thao tác vừa nêu ở trên.Dữ liệu: Vào từ file văn bản ROOM.INP theo qui cách như sau: • Dòng thứ nhất ghi số nguyên dương N (1 N 300) là số các nhà tỷ phú đi đánh golf. • Dòng thứ hai ghi N số Si (1 Si  1000000) (i=1..N) cách nhau bởi dấu cách, tương ứng là số chứng minh thư của N nhà tỷ phú.Kết quả: Ghi ra file văn bản ROOM.OUT một số nguyên M, là số lượng phòng ít nhất giámđốc khu nghỉ mát phải sử dụng ứng với dữ liệu vào đã cho.Ví dụ: ROOM.INP ROOM.OUT2 346Bài 3. Nhà hóa họcTrên mảnh đất thần thoại của Alice, các chất hóa học có thể kết hợp với nhau để sinh ra cácchất khác, ví dụ kết hợp sắt với nước để sinh ra vàng. Có 26 chất hóa học được ký hiệu từ Ađến Z và N phản ứng hóa học có thể sử dụng được đánh số từ 1 đến N (1 N 100). Mỗiphản ứng kết hợp đều có chung một dạng - có hai chất tham gia phản ứng và nhận được haichất sau phản ứng, ví dụ: A + B sinh ra C + BLưu ý, do các phản ứng từ 1 đến N được thực hiện dưới các N điều kiện khác nhau, có thể tồntại 2 phản ứng với cùng hai chất tham gia phản ứng nhưng nhận được 2 chất sau phản ứngkhác nhau. Ví dụ, phản ứng thứ i: A + B sinh ra C + B,phản ứng thứ j: A + B sinh ra E + FMột tên nhà giàu tham lam nhưng rất dốt hóa học muốn biến 4 chất hắn có thành vàng (kýhiệu là V). Hắn bắt cóc một nhà hóa học và bắt nhà hóa học này thực hiện lòng tham của hắn.Yêu cầu: Hãy giúp nhà hóa học đưa ra các phản ứng kết hợp để tạo ra vàng. Nếu không thểtìm ra quá trình đó hãy thông báo là không thể tạo ra vàng.Dữ liệu: Vào từ file văn bản GOLD.INP theo qui cách như sau: • Dòng thứ nhất ghi số nguyên dương N, là số phản ứng kết hợp có thể sử dụng. • Dòng thứ i trong N dòng tiếp theo mô tả phản ứng thứ i gồm bốn chữ cái, 2 chữ cái đầu là tên 2 chất tham gia phản ứng, 2 chữ cái sau là tên 2 chất được tạo ra sau phản ứng đó. Các chữ cái ghi cách nhau bởi dấu cách. 2 • Dòng cuối cùng ghi bốn chữ cái, là tên của bốn chất tên nhà giàu có ban đầu.Kết quả: Đưa ra trên file văn bản GOLD.OUT. Dòng đầu tiên ghi số lượng các phản ứng nhàhóa học sẽ sử dụng để tạo ra vàng. Dòng thứ hai ghi ra số hiệu các phản ứng theo thứ tự đượcsử dụng, cách nhau bởi dấu cách. Nếu không tồn tại một qui trình, hãy ghi ra một số nguyênduy nhất -1.Ví dụ: GOLD.INP GOLD.OUT2 ...