Title LỜI GIẢI THAM KHẢO MÔN CHUYÊN TIN LẬP TRÌNH.pdf ✅

1 Kì thi tuyển sinh vào lớp 10 năm học 2024-2025 tỉnh Tiền Giang LỜI GIẢI THAM KHẢO MÔN CHUYÊN TIN – LẬP TRÌNH Thực hiện. Lê Nhất Duy – Nguyễn Duy Khang 1. Bài 1: PHÉP TOÁN (2 điểm) 1.1. Đề bài Bi đang học về các phép toán số học. Thầy giáo cho Bi bài toán như sau: “Gọi S là tổng các số tự nhiên từ 1 đến n. Lấy S đem chia cho số nguyên dương k thì được thương nguyên và số dư là bao nhiêu?” Em hãy giúp Bi giải bài toán này nhé! Dữ liệu vào: Đọc từ file DIVMOD.INP gồm một dòng chứa hai số nguyên dương n và k (n, k ≤ 109 ). Kết quả ra: Ghi vào file DIVMOD.OUT một dòng gồm hai số nguyên tương ứng là thương nguyên và số dư cần tìm. Lưu ý: Các số cùng dòng cách nhau bởi một khoảng trắng. Ví dụ: DIVMOD.INP DIVMOD.OUT Giải thích 5 2 7 1 Với n = 5, ta có S = 1 + 2 + 3 + 4 + 5 = 15. 15 chia cho 2 được thương nguyên là 7 và số dư là 1. Giới hạn: • 40% số test có n, k ≤ 103 • 30% số test tiếp theo có 103 < n, k ≤ 106 • 30% số test tiếp theo có 106 < n, k ≤ 109 1.2. Lời giải Subtask 1, 2: Duyệt các số nguyên dương từ 1 đến n để tính tổng S. Sau đó dùng phép chia lấy phần nguyên và phép chia lấy phần dư để tính kết quả. → Độ phức tạp: O(n). Subtask 3: Bằng quy nạp, ta có thể chứng minh rằng S = 1 + 2 + ⋯ + n = n(n+1) 2 . Từ đó ta rút ngắn thời gian ở bước duyệt. → Độ phức tạp: O(1).
LỜI GIẢI THAM KHẢO MÔN CHUYÊN TIN LẬP TRÌNH 2 1.3. Code tham khảo 2. Bài 2: TÌM X (2 điểm) 2.1. Đề bài Với một số nguyên dương X, ta gọi [√X] là phần nguyên căn bậc hai của X. Ví dụ: X = 10 thì [√X] = 3; X = 25 thì [√X] = 5. Bi có một số nguyên dương n. Bi muốn tìm ra số nguyên dương X sao cho: X + [√X] = n Theo em, số X mà Bi tìm được là số nào? Dữ liệu vào: Đọc từ file NUMX.INP gồm một số nguyên dương n (n ≤ 1012). Kết quả ra: Ghi vào file NUMX.OUT số nguyên dương X mà Bi tìm được. Biết rằng dữ liệu vào đảm bảo luôn tìm được một giá trị nguyên dương X. Ví dụ: NUMX.INP NUMX.OUT Giải thích 13 10 Với n = 13, ta có X = 10 vì 10 + [√10] = 13 = n. Giới hạn: • 40% số test có n ≤ 103
LỜI GIẢI THAM KHẢO MÔN CHUYÊN TIN LẬP TRÌNH 3 • 30% số test tiếp theo có 103 < n ≤ 106 • 30% số test tiếp theo có 106 < n ≤ 1012 2.2. Lời giải Subtask 1, 2: Duyệt các số nguyên dương X từ 1 đến n và kiểm tra có thỏa đẳng thức đề bài hay không. → Độ phức tạp: O(n). Subtask 3: Nhận xét: Nếu X + [√X] = n thì X ≥ n − √n. Thật vậy, giả sử X < n − √n thì ta có [√X] ≤ √X < √n − √n < √n. Khi đó X + [√X] < n − √n + √n = n, điều này mâu thuẫn. Do đó ta có nhận xét trên đúng. Từ đó, ta chỉ cần duyệt ngược từ n về n − √n và kiểm tra như subtask trên, không quá √n bước sẽ tìm được đáp án. → Độ phức tạp: O(√n). 2.3. Code tham khảo
LỜI GIẢI THAM KHẢO MÔN CHUYÊN TIN LẬP TRÌNH 4 3. Bài 3: BÀI TẬP (2 điểm) 3.1. Đề bài Bi có quyển sách tin học rất hay. Quyển sách gồm n bài tập được đánh số từ 1 đến n. Bi chọn những bài dễ giải trước. Bi giải được k bài trong số n bài đó (k < n). Hôm nay, Bi muốn thống kê xem những bài nào mình chưa giải để hè này Bi sẽ cố gắng giải cho hết. Em hãy giúp Bi liệt kê các bài chưa giải nhé! Dữ liệu vào: Đọc từ file EXERCISE.INP gồm: + Dòng thứ nhất chứa hai số nguyên dương n và k (1 ≤ k < n ≤ 106 ). + Dòng thứ hai chứa k số nguyên dương a1, a2, ... , ak, các giá trị đôi một khác nhau (1 ≤ ai ≤ n, 1 ≤ i ≤ k). Kết quả ra: Ghi vào file EXERCISE.OUT gồm một dòng ghi các số nguyên dương là những bài tập Bi chưa giải và ghi theo thứ tự từ bé đến lớn. Lưu ý: Các số cùng dòng cách nhau bởi một khoảng trắng. Ví dụ: EXERCISE.INP EXERCISE.OUT Giải thích 7 3 1 4 2 3 5 6 7 Với n = 7, k = 3, có 7 bài tập, Bi đã giải 3 bài là: 1 4 2. Các bài tập chưa giải là: 3 5 6 7. Giới hạn: • 40% số test có n ≤ 102 • 30% số test tiếp theo có 102 < n ≤ 103 • 30% số test tiếp theo có 103 < n ≤ 106 3.2. Lời giải Subtask 1, 2: Duyệt các số nguyên dương x từ 1 đến n, với mỗi x duyệt dãy a1, a2, ... , ak xem có tồn tại ai = x hay không. Nếu không thì in ra x. → Độ phức tạp: O(n 2 ). Subtask 3: Sử dụng thuật toán đếm phân phối. Dùng một mảng d[] với ý nghĩa: d[x] = 1 nếu bài tập x đã hoàn thành và d[x] = 0 nếu bài tập chưa được hoàn thành. Duyệt các ai và đánh dấu tất cả d[ai ] = 1. Sau đó duyệt các số nguyên dương x từ 1 đến n, nếu d[x] = 0 thì in ra x. → Độ phức tạp: O(n).