Tài liệu gồm 3 bài thi lập trình bảng C cấp phổ thông trung học do Hội thi tin học trẻ cấp quận năm 2016 tổ chức. Tài liệu nhằm phục vụ cho các bạn ôn luyện thật tốt trước kì thi diễn ra. . | HỘI THI TIN HỌC TRẺ CẤP QUẬN NĂM 2016 Đề thi lập trình Bảng C: Phổ thông Trung học Thời gian thi: 150 phút Đề thi gồm 03 trang (Không sử dụng tài liệu) TỔNG QUAN ĐỀ THI Tên bài Tên file chương trình Tên file dữ liệu Tên file kết quả Thời gian cho mỗi test Tam giác TAMGIAC.??? 1 giây Số may mắn MAYMAN.??? 1 giây Bài tập BAITAP.??? 1 giây Lưu ý: ??? được thay thế là PAS nếu là ngôn ngữ PASCAL hoặc CPP nếu là ngôn ngữ C/C++ File dữ liệu, file kết quả được đặt ở thư mục hiện hành. Giám thị coi thi không giải thích gì thêm Lập trình thực hiện các công việc sau đây: BÀI 1. TAM GIÁC Tên tập tin chương trình TAMGIAC.??? Cho N điểm phân biệt trên mặt phẳng, hãy đếm xem có bao nhiêu cách chọn 3 điểm sao cho 3 điểm được chọn tạo thành một tam giác vuông với 2 cạnh góc vuông song song với trục tọa độ. Dữ liệu vào: Từ file - Dòng đầu là số N(1 ≤ N ≤ 105) - số lượng điểm. - N dòng tiếp theo, mỗi dòng chứa một cặp số X và Y (1 ≤ X, Y ≤ 105), tọa độ của một điểm. Dữ liệu vào đảm bảo không có 2 điểm trùng nhau. Kết quả: Ghi vào file Số cách chọn thỏa yêu cầu. 6 10 10 20 10 10 20 20 20 30 20 30 30 8 3 4 2 2 1 1 3 0 Scoring: • Số lượng test có N ≤ 100 chiếm 40% số điểm. • Số lượng test có N ≤ 104 chiếm 70% số điểm. BÀI 2. SỐ MAY MẮN Tên tập tin chương trình MAYMAN.??? Số X gọi là may mắn nếu tổng giá trị các chữ số của X bằng S. Hãy cho biết có bao nhiêu số nguyên nằm trong đoạn [A, B] là số may mắn, đồng thời tìm số nhỏ nhất thỏa yêu cầu trên. Dữ liệu vào: Từ file Gồm 3 số A, B, S (1 ≤ A ≤ B < 1015, 1 ≤ S ≤ 135) Kết quả: Ghi vào file 1 9 5 1 5 1 100 10 9 19 11111 99999 24 5445 11499 BÀI 3. BÀI TẬP Tên tập tin chương trình BAITAP.??? Ban tổ chức cần chuẩn bị đề cho một loạt các kỳ thi, mỗi kỳ thi gồm đúng 4 bài tập. Mỗi bài tập có một chỉ số độ khó nhất định được biểu diễn bằng các số từ 1 đến 100, chỉ số càng cao thì bài tập đó càng khó. Trong mỗi kỳ thi, độ khó của các bài tập phải tăng dần và tăng không quá 10. Nói cách khác giả sử kỳ thi gồm 4 bài tập với độ khó a, b, c, d (theo thứ tự), các điều kiện sau phải thỏa: a < b < c < d, b – a <= 10, c – b <= 10, d – c <= 10. Bạn được cho một danh sách gồm N bài tập. Bạn được phép chèn thêm bài tập ở bất kỳ vị trí nào trong danh sách nhưng bạn không được làm thay đổi thứ tự của các bài tập có sẵn. Bạn cần thêm vào ít bài tập nhất sao cho số lượng bài tập chia hết cho 4 và 4 bài tập đầu tiên có thể tạo thành một kỳ thi hợp lệ, tương tự 4 bài tập tiếp theo, và 4 bài tập tiếp theo sau đó cũng có thể tạo thành kỳ thi hợp lệ. Dữ liệu vào: Từ file Dòng đầu tiên chứa một số nguyên dương N. Dòng tiếp theo chứa N số nguyên cách nhau bởi khoảng trắng. Số nguyên thứ i, D_i, tượng trưng cho độ khó của bài tập thứ i. Kết quả: Ghi vào file Một số nguyên duy nhất là số bài tập ít nhất cần thêm vào. Giới hạn: N <= 100000 1 <= D_i <= 100 Ví dụ: 4 10 15 25 30 0 4 15 20 25 40 4 3 3 3 3 9 8 60 90 61 62 63 91 92 93 4 Giải thích: Ở ví dụ 2, độ khó của bài tập thứ 3 và bài tập thứ 4 cách nhau 15 nên ta cần thêm vào 4 bài tập. Một trong những cách thêm là [15 20 25 30 30 35 40 45] Các bài tập thêm vào được gạch chân, với danh sách như vậy, 4 bài tập đầu tiên (15, 20, 25, 30) có thể tạo thành một kỳ thi hợp lệ và 4 bài tập tiếp theo cũng vậy HẾT Trang 2/3
