Đề thi HSG tin học - THPT Nguyễn Trí Thanh

Xin giới thiệu với các bạn Đề thi HSG tin học - THPT Nguyễn Trí Thanh

Đề bài 

BÀI 1: SỐ THÂN THIỆN

Đang tìm hiểu các thuật toán về số tự nhiên, Nguyên phát hiện ra số tự nhiên có rất nhiều tính chất thú vị. Ví dụ số hoàn hảo có tính chất: tổng các ước bằng 2 lần số đó, như số 6, số 24… Nhiều số tự nhiên khi tìm ước chung lớn nhất với số đảo ngược của nó bằng 1, những số như thế được gọi là số thân thiện. Chẳng hạn số 23, số đảo ngược của nó là 32, hai số này có ước chung lớn nhất là 1 nên số 23 là số thân thiện và 32 cũng là số thân thiện.

Yêu cầu: Cho 2 số tự nhiên a, b (10 ≤ a ≤ b ≤ 10⁴). Hãy đếm xem trong đoạn từ a đến b có bao nhiêu số thân thiện.

Ví dụ:

Dữ liệu vào	Kết quả	Giải thích
19   29	4	Đó là các số: 19, 23, 25, 29

 

BÀI 2: SỐ TỰ NHIÊN NHỎ NHẤT

Nam một người bạn của Nguyên đang tìm cách giải một bài toán liên quan tới số tự nhiên và cần sự giúp đỡ của Nguyên, nhưng thử thách lần này là một dãy gồm N số tự nhiên bất kỳ nằm trong đoạn từ 0 tới 10⁹, tìm số tự nhiên nhỏ nhất không có trong dãy số đó. Vì số lượng các số tự nhiên trong dãy số đã cho có thể lên tới 10⁶ phần tử nên việc tìm thủ công là không thể mà cần một thuật toán để cài đặt vào máy tính và nhờ máy tính tìm giúp.

Yêu cầu: Cho một dãy A gồm N (1 ≤ N ≤ 10⁶) số tự nhiên. Hãy tìm số tự nhiên nhỏ nhất không xuất hiện trong dãy A.

 Ví dụ:

Dữ liệu vào	Kết quả
N= 5 Dãy số:   5  4  2  3  1	0
N= 9 Dãy số: 2  4  0  3  1  2  6  2   8	5

 

BÀI 3: SỐ LƯỢNG NHÓM ĐỀ TÀI

Nhà trường phát động phong trào đăng ký làm sáng tạo khoa học kỹ thuật, tất cả các bạn trong lớp của Nguyên đều tích cực tham gia và được phân công vào các nhóm đề tài. Mỗi nhóm đề tài được ký hiệu: <Tên nhóm> <Số thành viên>, ví dụ Nguyên được phân công vào nhóm TIN gồm 3 thành viên thì ký hiệu nhóm là TIN 3. Danh sách được lập ra gồm ký hiệu nhóm và tên thành viên, nhưng trong quá trình in ấn cột ký hiệu nhóm bị mờ <tên nhóm> và không đọc được chỉ còn lại <số thành viên>.

Ví dụ:

Ký   hiệu	Thành viên		hiệu	Thành viên
TIN 3	Việt		3	Việt
TOAN 2	Tuấn		2	Tuấn
TIN 3	Thái	Do lỗi in ấn →	3	Thái
TIN 3	Anh		3	Anh
TOAN 2	Chính		2	Chính

 

Yêu cầu: Cho danh sách gồm n học sinh và số thành viên của nhóm tương ứng với từng học sinh. Hãy xác định số lượng nhóm đề tài đã được phân công. Dữ liệu đảm bảo bài toán có nghiệm.

Ví dụ:

Dữ liệu vào	Kết quả
N= 5 3  2  3  3  2	2
N= 10 5  1  2  5  5  2  5  5  2  2	4

Hướng dẫn giải Đề thi HSG tin học - THPT Nguyễn Trí Thanh

Câu 1:

Xác định bài toán:

• Input: Hai số a, b (10 ≤ a ≤ b ≤ 10⁴)


• Output: Số lượng số thân thiện thuộc đoạn [a,b]

Ý tưởng: Dùng 1 biến dem để lưu số lượng số thân thiện

• Xét lần lượt các số tự nhiên i từ a tới b


• Với mỗi số i xác định số tự nhiên j là đảo ngược của i


• Nếu UCLN(i,j)= 1 thì tăng biến dem lên 1


• Kết quả bài toán là dem

Thuật toán:

• Bước 1. Nhập hai số a và b;


• Bước 2. i = a; dem  =  0;


• Bước 3. Nếu i>b thì chuyển đến bước 13;


• Bước 4. k = i, Songuoc = 0;


• Bước 5. Nếu k = 0 thì chuyển đến bước 8;


• Bước 6. Songuoc = Songuoc*10+k mod 10;


• Bước 7. k  =  k div 10; rồi quay lại bước 5


• Bước 8. k  =  i;


• Bước 9. Nếu k = Songuoc thì chuyển đến bước 11;


• Bước 10. Nếu k > Songuoc thì  k  =  k - Songuoc, Ngược lại Songuoc  =  Songuoc – k, rồi quay lại bước 9;


• Bước 11. Nếu k=1 thì dem  =  dem+1;


• Bước 12. i = i+1 và quay lại bước 3;


• Bước 13. Đưa ra kết quả dem rồi kết thúc.

Câu 2:

Xác định bài toán:

• Input: N và dãy A gồm N số tự nhiên


• Output: Số tự nhiên nhỏ nhất không xuất hiện trong dãy A

Ý tưởng:

Nhận xét: Số tự nhiên nhỏ nhất luôn nằm trong đoạn từ 0 tới N.

Do vậy dùng dãy B[0..N] để đánh dấu những số đã có trong dãy A nằm trong đoạn từ 0 tới N. Ban đầu đánh dấu tất cả các phần tử của dãy B có giá trị là False. Tiếp theo đánh dấu trong dãy B những phần tử có trong dãy A như sau:

Xét i: 1 tới N, nếu A_i<=N thì đánh dấu B[A_i]ßTrue

Tìm số tự nhiên đầu tiên j trong dãy B mà Bj=False, với j: 0 tới N

Thuật toán:

• Bước 1. Nhập N và dãy A₁, A₂,...,A_N;


• Bước 2. i=0;


• Bước 3. Nếu i>N thì chuyển đến bước 6;


• Bước 4. B_{i =} False;


• Bước 5. i = i+1; rồi quay lại bước 3;


• Bước 6. i=1;


• Bước 7. Nếu i>N thì và chuyển đến bước 10;


• Bước 8. Nếu A_i<=N thì B[A_i]=true;


• Bước 9. i=i+1 và quay lại bước 7;


• Bước 10. j=0;


• Bước 11. Nếu B_j=false thì thông báo j, rồi kết thúc;


• Bước 12. j=j+1 và quay lại bước 11;

Câu 3:

Xác định bài toán:

• Input: N và dãy A gồm N số nguyên dương lưu số thành viên


•  Output: Số lượng nhóm đề tài

Ý tưởng:

• Xét lần lượng từng học sinh:1 .. N


•   Ứng với từng học sinh đánh dấu các học sinh cùng nhóm, đồng thời tăng biến dem lên 1.


•  Kết quả bài toán là dem

Thuật toán:

• Bước 1. Nhập N và dãy A₁, A₂,...,A_N;


• Bước 2. i = 1; dem  =  0;


• Bước 3. Nếu i>N thì chuyển đến bước 11;


• Bước 4: Nếu A_i<=0 thì chuyển sang bước thứ 10;


• Bước 5. dem  =  dem+1;


• Bước 6. K = A_i;  j  =  i; d  =  0;


• Bước 7. Nếu (j>N) hoặc (d=K) thì và chuyển đến bước 10;


• Bước 8. Nếu A_j=k thì A_j  =  -K; d  =  d+1;


• Bước 9. j = j+1 và quay lại bước 7;


• Bước 10. i = i+1 và quay lại bước 3


• Bước 11. Đưa ra kết quả dem  rồi kết thúc.