Đề thi lập trình cá nhân cấp câu lạc bộ Olympic Tin học HUTECH - Tháng 2

KÌ THI LẬP TRÌNH CÁ NHÂN CẤP CÂU LẠC BỘ OLYMPIC TIN HỌC HUTECH<br /> ĐỀ CHÍNH THỨC – THÁNG 2<br /> KÌ THI LẬP TRÌNH CÁ NHÂN THÁNG 2<br /> CLB OLYMPIC TIN HỌC HUTECH<br /> ---o0o---<br /> <br /> NỘI QUY<br /> <br />  Đề thi gồm 5 bài (từ BÀI 1 đến BÀI 5). Các thí sinh đọc kĩ đề và thực hiện theo yêu cầu<br /> đề. Lưu ý: sử dụng thiết bị nhập/xuất chuẩn (bàn phím/màn hình), không sử dụng tệp<br /> tin để chứa dữ liệu nhập xuất. Thời gian làm bài: từ 18h30 đến 22h30 ngày 20/02/2017.<br />  Các thí sinh tiến hành nộp bài làm (tệp .CPP) cho ban tổ chức sau khi đã làm hết các bài<br /> mình có thể làm về đường dẫn sau: http://tinyurl.com/j3gqk9u<br />  Lưu ý: các bài thi phải được nằm chung 1 thư mục là họ tên của thí sinh. Ví dụ: thí sinh<br /> Nguyễn Văn A thì tạo 1 thư mục tên NguyenVanA, bên trong gồm các tệp như BAI1.CPP,<br /> BAI2.CPP, BAI3.CPP,… Sau đó, thí sinh tiến hành nén thư mục trên và gửi cho ban tổ<br /> chức (Mục “Name” ghi họ tên, ví dụ NguyenVanA; mục “Email Address” không cần ghi).<br /> Các thí sinh chỉ được nộp duy nhất một tệp nén chứa các bài làm. Trường hợp thí sinh<br /> muốn cập nhật lại bài thi (bổ sung bài đã làm được), vui lòng nộp lại theo hướng dẫn trên,<br /> nhưng đặt tên thư mục là NguyenVanA(1), thí sinh chỉ được phép bổ sung một lần.<br /> Chúc các thí sinh hoàn thành tốt bài thi của mình!<br /> <br /> TỔNG QUAN VỀ ĐỀ THI<br /> Bài<br /> BÀI 1<br /> BÀI 2<br /> BÀI 3<br /> BÀI 4<br /> BÀI 5<br /> <br /> Tên bài<br /> SỐ NGUYÊN TỐ<br /> DÃY SỐ TĂNG<br /> XÂU ÍT NHẤT<br /> THẺ THÀNH VIÊN<br /> TÍNH TỔNG<br /> <br /> Tên chương trình<br /> BAI1.CPP<br /> BAI2.CPP<br /> BAI3.CPP<br /> BAI4.CPP<br /> BAI5.CPP<br /> <br /> Số test<br /> 10<br /> 10<br /> 10<br /> 10<br /> 10<br /> <br /> Thời gian chạy<br /> 1 giây<br /> 1 giây<br /> 1 giây<br /> 1 giây<br /> 1 giây<br /> <br /> BÀI 1: SỐ NGUYÊN TỐ<br /> Trong giờ học toán của mình, Trang rất hứng thú với số nguyên tố. Biết rằng<br /> số nguyên tố là số có hai ước là 1 và chính nó. Trang muốn biết rằng tổng các số<br /> nguyên tố nhỏ hơn một số N cho trước là bao nhiêu. Vì cũng yêu thích lập trình nên<br /> cô ta quyết định viết chương trình trên máy tính. Tuy nhiên, vấn đề mà Trang gặp<br /> phải là thời gian chạy của chương trình mà mình viết quá lâu. Bất lực, Trang đành<br /> nhờ đến sự giúp đỡ của các thành viên Câu lạc bộ Olympic Tin học HUTECH. Các<br /> bạn hãy giúp Trang giải quyết bài toán này nhé.<br /> Dữ liệu vào: Ghi số nguyên dương N (N < 3.10 7 ).<br /> Dữ liệu ra: Gồm 1 dòng là tổng các số nguyên tố nhỏ hơn N.<br /> Ví dụ:<br /> INPUT<br /> OUTPUT<br /> 4<br /> 5<br /> Giải thích: Các số nguyên tố nhỏ hơn 4 là 2 và 3, do đó xuất ra kết quả là 5.<br /> Ràng buộc:<br />  40% số test có N < 40.000.<br /> CLB OLYMPIC TIN HỌC HUTECH ®<br /> <br /> Trang 1 của 3<br /> <br /> KÌ THI LẬP TRÌNH CÁ NHÂN CẤP CÂU LẠC BỘ OLYMPIC TIN HỌC HUTECH<br /> ĐỀ CHÍNH THỨC – THÁNG 2<br />  30% số test có N < 900.000.<br />  30% số test có N < 30.000.000.<br /> <br /> BÀI 2: DÃY SỐ TĂNG<br /> Cho trước hai dãy số nguyên A, B có cùng số phần tử N (N < 5.10 5 ). Cho trước<br /> giá trị của phần tử lớn nhất trong cả hai dãy không quá 10000. Hãy tạo ra một dãy C<br /> có kết quả là hòa hai dãy A và B sao cho các phần tử trong C có giá trị tăng dần.<br /> Dữ liệu vào: Gồm 3 dòng:<br />  Dòng thứ 1 ghi số nguyên dương N (N < 5.10 5 ).<br />  Dòng thứ 2 ghi giá trị của các phần tử trong dãy A, mỗi số cách nhau 1 khoảng<br /> trắng.<br />  Dòng thứ 3 ghi giá trị của các phần tử trong dãy B, mỗi số cách nhau 1 khoảng<br /> trắng.<br /> Dữ liệu ra: Ghi các giá trị của các phần tử dãy C, mỗi số cách nhau 1 khoảng trắng.<br /> Ví dụ:<br /> INPUT<br /> OUTPUT<br /> 6<br /> 1 2 4 4 6 7 9 10 15 21 24 30<br /> 6 4 2 9 24 30<br /> 1 4 7 21 15 10<br /> Ràng buộc :<br />  50% số test có N < 1.000.<br />  50% số test có N < 100.000.<br /> <br /> BÀI 3: XÂU ÍT NHẤT<br /> Cho trước một số nguyên dương N (N ≤ 100), hãy tìm 1 xâu chỉ gồm các ký tự<br /> A, B, C thõa mãn 3 điều kiện:<br />  Có độ dài N.<br />  Hai đoạn con bất kỳ liên tiếp nhau đều khác nhau.<br />  Có ít ký tự B nhất.<br /> Nhiệm vụ của bạn là tìm ra số ký tự B (ít nhất).<br /> Dữ liệu vào: Gồm 1 dòng duy nhất ghi số nguyên dương N (N ≤ 100).<br /> Dữ liệu ra: Gồm 1 dòng duy nhất ghi số kí tự B ít nhất tìm được.<br /> Ví dụ:<br /> INPUT<br /> OUTPUT<br /> 10<br /> 2<br /> Giải thích: ACABACBCAC.<br /> <br /> BÀI 4: THẺ THÀNH VIÊN<br /> Khoa Công nghệ thông tin trường Đại học Công nghệ Tp.HCM (HUTECH) có một<br /> Câu lạc bộ chuyên về lập trình và các thuật toán là Câu lạc bộ Olympic Tin học. Câu lạc bộ<br /> có nhiều thành viên tham gia, mỗi thành viên của Câu lạc bộ đều được cấp một Thẻ thành<br /> viên và mỗi thẻ có 1 mã số đặc biệt.<br /> Mã số của thành viên của Câu lạc bộ là một số nguyên dương k thỏa mãn:<br />  k + 1 là một số nguyên tố.<br /> CLB OLYMPIC TIN HỌC HUTECH ®<br /> <br /> Trang 2 của 3<br /> <br /> KÌ THI LẬP TRÌNH CÁ NHÂN CẤP CÂU LẠC BỘ OLYMPIC TIN HỌC HUTECH<br /> ĐỀ CHÍNH THỨC – THÁNG 2<br />  Tổng k với một số chính phương nào đó là tích của 4 số nguyên liên tiếp:<br />