KÌ THI LẬP TRÌNH CÁ NHÂN CẤP CÂU LẠC BỘ OLYMPIC TIN HỌC HUTECH ĐỀ CHÍNH THỨC – THÁNG 2
KÌ THI LẬP TRÌNH CÁ NHÂN THÁNG 2 CLB OLYMPIC TIN HỌC HUTECH ---o0o---
NỘI QUY Đề 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 đề. 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 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. 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 mình có thể làm về đường dẫn sau: http://tinyurl.com/j3gqk9u
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 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, BAI2.CPP, BAI3.CPP,… Sau đó, thí sinh tiến hành nén thư mục trên và gửi cho ban tổ chức (Mục “Name” ghi họ tên, ví dụ NguyenVanA; mục “Email Address” không cần ghi). 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 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, nhưng đặt tên thư mục là NguyenVanA(1), thí sinh chỉ được phép bổ sung một lần.
Chúc các thí sinh hoàn thành tốt bài thi của mình! TỔNG QUAN VỀ ĐỀ THI
Bài
Tên bài BÀI 1 SỐ NGUYÊN TỐ BÀI 2 DÃY SỐ TĂNG BÀI 3 XÂU ÍT NHẤT BÀI 4 THẺ THÀNH VIÊN BÀI 5 TÍNH TỔNG Tên chương trình Số test Thời gian chạy BAI1.CPP BAI2.CPP BAI3.CPP BAI4.CPP BAI5.CPP 1 giây 1 giây 1 giây 1 giây 1 giây 10 10 10 10 10
BÀI 1: SỐ NGUYÊN TỐ
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 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ố 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 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 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 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 bạn hãy giúp Trang giải quyết bài toán này nhé. Dữ liệu vào: Ghi số nguyên dương N (N < 3.107). Dữ liệu ra: Gồm 1 dòng là tổng các số nguyên tố nhỏ hơn N. Ví dụ:
INPUT 4 OUTPUT 5
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. Ràng buộc:
40% số test có N < 40.000.
CLB OLYMPIC TIN HỌC HUTECH ® Trang 1 của 3
KÌ THI LẬP TRÌNH CÁ NHÂN CẤP CÂU LẠC BỘ OLYMPIC TIN HỌC HUTECH ĐỀ CHÍNH THỨC – THÁNG 2
30% số test có N < 900.000. 30% số test có N < 30.000.000.
BÀI 2: DÃY SỐ TĂNG
Cho trước hai dãy số nguyên A, B có cùng số phần tử N (N < 5.105). Cho trước 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 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. Dữ liệu vào: Gồm 3 dòng:
Dòng thứ 1 ghi số nguyên dương N (N < 5.105). 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
trắng.
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
trắng.
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. Ví dụ:
INPUT
OUTPUT 1 2 4 4 6 7 9 10 15 21 24 30
6 6 4 2 9 24 30 1 4 7 21 15 10
Ràng buộc :
50% số test có N < 1.000. 50% số test có N < 100.000.
BÀI 3: XÂU ÍT NHẤT
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ự A, B, C thõa mãn 3 điều kiện:
Có độ dài N. Hai đoạn con bất kỳ liên tiếp nhau đều khác nhau. Có ít ký tự B nhất.
Nhiệm vụ của bạn là tìm ra số ký tự B (ít nhất). Dữ liệu vào: Gồm 1 dòng duy nhất ghi số nguyên dương N (N ≤ 100). Dữ liệu ra: Gồm 1 dòng duy nhất ghi số kí tự B ít nhất tìm được. Ví dụ:
INPUT OUTPUT
10 2
Giải thích: ACABACBCAC. BÀI 4: THẺ THÀNH VIÊN
Khoa Công nghệ thông tin trường Đại học Công nghệ Tp.HCM (HUTECH) có một 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ộ 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 viên và mỗi thẻ có 1 mã số đặc biệt. 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:
k + 1 là một số nguyên tố.
CLB OLYMPIC TIN HỌC HUTECH ® Trang 2 của 3
KÌ THI LẬP TRÌNH CÁ NHÂN CẤP CÂU LẠC BỘ OLYMPIC TIN HỌC HUTECH ĐỀ CHÍNH THỨC – THÁNG 2
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:
𝑘 + 𝑦2 = 𝑥(𝑥 + 1)(𝑥 + 2)(𝑥 + 3) Yêu cầu: Cho một mã số của một sinh viên trong trường, bạn hãy kiểm tra xem sinh viên đó có thuộc Câu lạc bộ Olympic Tin học không? Dữ liệu vào: Ghi một số nguyên là mã số của một sinh viên trong trường. Dữ liệu ra: Nếu là thành viên Câu lạc bộ Olympic Tin học thì in ra YES, ngược lại in ra NO. Ví dụ:
INPUT OUTPUT
36 10 YES NO
Giải thích ví dụ 1: 36 + 1 = 37 là số nguyên tố, 36 + 182 = 3.4.5.6. BÀI 5: TÍNH TỔNG
Cho dãy số định nghĩa như sau : 1 22−1 1 (𝑛+1)2−1
𝑈1 = 𝑈𝑛 = Với số n là các số nguyên dương cho trước.
Yêu cầu: Hãy tính tổng các phần tử của dãy sau: 𝑆 = 𝑈1 + 𝑈2 + ⋯ + 𝑈𝑛. Kết quả in ra là một
phân số rút gọn về tối giản với dạng
INPUT OUTPUT 21/40
3 8⁄ + 1 3⁄ + 1 40⁄ . 15⁄ = 21 Giải thích: 𝑆 = 1
---HẾT---
CLB OLYMPIC TIN HỌC HUTECH ® Trang 3 của 3
