onthicaptoc.com De thi HSG Tin chuyen 12 Quang Nam 2023
TỔNG QUAN ĐỀ THI
Lưu ý: Dấu * trong phần tên chương trình tương ứng với ngôn ngữ lập trình mà thí sinh sử dụng, ví dụ PAS, CPP, …
Bài 1. Bộ số học
Cô giáo Hoa đang giảng bài : “Ước số và bội số là một trong những khái niệm quen thuộc trong số học. Với 2 số nguyên A và B bất kỳ, nếu A chia hết cho B, ta nói A là bội số của B và B là ước số của A. Với một bộ K số nguyên dương a1, a2,…, aK bất kỳ, ước số chung lớn nhất của chúng là số nguyên X lớn nhất thỏa mãn mọi ai là bội số của X. Tương tự, bội số chung nhỏ nhất của bộ số này là số nguyên Y nhỏ nhất thỏa mãn mọi ai là ước số của Y”. Bất chợt học sinh Phát trong lớp nghĩ ra một bài toán: “Cho 2 dãy số nguyên p1, p2,…, pM và q1, q2,…, qN. Đặt P= p1*p2*…*pM và Q= q1*q2*…*qN. Đếm số bộ K số nguyên có ước số chung lớn nhất là P và bội số chung nhỏ nhất là Q”.
Yêu cầu: Các bạn là học sinh tuyển chọn của trường hãy giúp Phát giải bài toán này nhé.
Dữ liệu vào: Từ tệp văn bản SOHOC.INP gồm:
Dòng đầu tiên gồm ba số nguyên dương M, N, K;
Dòng thứ hai gồm M số nguyên dương p1,p2,…, pM;
Dòng thứ ba gồm N số nguyên dương q1, q2,…, qN.
Các số trên một dòng của tệp dữ liệu vào được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra tệp văn bản SOHOC.OUT gồm: Một số nguyên duy nhất là số bộ số thỏa mãn. Kết quả của bài toán chỉ cần in ra phần dư khi chia cho 109+9.
Ví dụ:
Ràng buộc: Trong tất cả bộ test: K≤109, các số còn lại trong tệp dữ liệu vào có giá trị tuyệt đối không quá 106.
Có 10% số test ứng với 10% số điểm của bài có M=N=K=1;
Có 30% số test ứng với 30% số điểm của bài có max(P, Q) ≤ 3x103 và K=2;
Có 20% số test ứng với 20% số điểm của bài có max(P, Q) ≤ 106 và K=2;
Có 20% số test ứng với 20% số điểm của bài có max(M, N) ≤ 5x103 và K=2;
Có 20% số test khác ứng với 20% số điểm còn lại của bài.
Bài 2. Đếm sỏi
Cô giáo dẫn một nhóm học sinh tới một sân gạch rộng của trường để vừa chơi vừa học. Sân gạch là một mặt phẳng hai chiều. Mỗi viên gạch là một ô vuông 1x1 đơn vị. Cô giáo nghĩ ra một trò chơi như sau: mỗi lượt cô sẽ đưa ra 4 số nguyên x1, y1, x2, y2 là tọa độ trái dưới (x1, y1) và phải trên (x2, y2) của một hình chữ nhật. Cô sẽ giao nhiệm vụ cho một đứa trẻ trong nhóm học sinh đi rải sỏi vào các viên gạch nằm trong hình chữ nhật đó, mỗi viên gạch rải 1 viên sỏi.
Đề thi hsg tin 9 quang năm 23 24