HSG lớp 9 Kon Tum 2022-2023

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH KON TUM Năm học 2022 - 2023

MÔN TIN HỌC 4 bài: RUTGON, HOITHAO, TAOXAU, CHUSO

Bài 1. Rút gọn phân số

Phân số a/b là tối giản nếu a và b là nguyên tố cùng nhau, nghĩa là a và b có ước số chung lớn nhất là 1.

Yêu cầu: Hãy viết chương trình thực hiện rút gọn phân số về dạng tối giản.

Dữ liệu: Vào từ file RUTGON.INP gồm hai số nguyên dương a, b (1 < a, b ≤ 10⁹).

Kết quả: Ghi ra file RUTGON.OUT gồm hai số nguyên dương tương ứng với tử số và mẫu số của phân số sau khi đã rút gọn.

Ví dụ:

RUTGON.INP	RUTGON.OUT	Giải thích
`12 18`	`2 3`	Rút gọn phân số 12/18 ta được phân số 2/3

Bài 2. Hội thao

Trong một đợt tổ chức hội thao cấp tỉnh dành cho học sinh trung học cơ sở, Ban Tổ chức hội thao đã nhận được sự hưởng ứng nhiệt tình của các bạn học sinh đến từ các trường học trung học cơ sở trên địa bàn tỉnh Kon Tum đăng ký tham gia với nhiều nội dung thi đấu. Có n học sinh đăng ký tham gia thi đấu tại hội thao. Các nội dung thi đấu được Ban Tổ chức hội thao đánh số từ 1 đến n và được phân loại theo nội dung thi đấu.

Theo kết quả phân loại, nội dung thi đấu thứ i được đặt tên là aᵢ (1 ≤ i ≤ n). Vì số lượng nội dung thi đấu tại hội thao lần này được học sinh đăng ký rất nhiều và đa dạng, nên việc bố trí trọng tài điều khiển các nội dung thi đấu tương đối khó khăn.

Yêu cầu: Bạn hãy giúp Ban Tổ chức hội thao xác định số nội dung thi đấu khác nhau và nội dung thi đấu có nhiều học sinh đăng ký nhất trong hội thao lần này.

Dữ liệu: Vào từ file HOITHAO.INP gồm hai dòng:

Dòng đầu tiên: chứa một số nguyên n (1 ≤ n ≤ 10⁶).
Dòng thứ hai: chứa n số nguyên a₁, a₂, …, aₙ tương ứng với các nội dung mà học sinh đăng ký thi đấu (1 ≤ aᵢ ≤ 10⁶, 1 ≤ i ≤ n).

Kết quả: Ghi ra file HOITHAO.OUT gồm 2 dòng:

Dòng thứ nhất: chứa số nguyên duy nhất chính là số nội dung khác nhau mà học sinh đăng ký thi đấu.
Dòng thứ hai: là số nguyên chính là nội dung thi đấu có nhiều học sinh đăng ký nhất (trường hợp có nhiều nội dung đăng ký nhiều nhất bằng nhau thì đưa ra nội dung ứng với số nhỏ nhất).

Ví dụ:

HOITHAO.INP	HOITHAO.OUT
`6` `1 4 4 2 5 4`	`4` `4`

Bài 3. Tạo xâu

Nam rất thích tạo ra các xâu kí tự. Bố Nam nghĩ ra câu đố thử thách trí thông minh và tính kiên trì của Nam như sau: từ xâu s ban đầu gồm n kí tự khác nhau từng đôi một (3 < n ≤ 52), hãy tạo ra các xâu mới khác bằng cách xóa đi không quá n − m kí tự (3 ≤ m < n) và giữ nguyên thứ tự các kí tự còn lại của xâu s.

Ví dụ: với xâu s = KHOA và m = 3 ta có thể tạo thành 5 xâu sau: KHO, KHA, KOA, HOA, KHOA.

Yêu cầu: Hãy giúp Nam đếm xem có bao nhiêu xâu được tạo ra từ xâu s theo cách như trên.

Dữ liệu: Vào từ file TAOXAU.INP gồm hai dòng:

Dòng đầu tiên: chứa hai số nguyên n, m (3 ≤ m < n ≤ 52).
Dòng thứ hai: chứa xâu s gồm n kí tự.

Kết quả: Ghi ra file TAOXAU.OUT gồm 1 số nguyên dương là số xâu khác nhau tạo được từ xâu s.

Ví dụ:

TAOXAU.INP	TAOXAU.OUT	Giải thích
`4 3` `KHOA`	`5`	Từ xâu KHOA có thể tạo được 5 xâu sau: KHO, KHA, KOA, HOA, KHOA.

Bài 4. Chữ số

Xét dãy các số tự nhiên a₀, a₁, …, aₙ được xây dựng theo quy tắc sau:

a₀ là một số tự nhiên cho trước có tối đa 10 chữ số.
Số aᵢ (i > 0) là một số tự nhiên nhận được từ aᵢ₋₁ bằng cách viết tiếp thêm vào sau số aᵢ₋₁ các chữ số của aᵢ₋₁ nhưng theo thứ tự ngược lại.

Ví dụ: Với a₀ = 123 thì a₁ = 123321, a₂ = 123321123321, a₃ = 123321123321123321123321.

Yêu cầu: Với hai số tự nhiên n và m cho trước, hãy tìm chữ số thứ m của aₙ.

Dữ liệu: Vào từ file CHUSO.INP gồm hai dòng:

Dòng thứ nhất: chứa số a₀.
Dòng thứ hai: chứa hai số tự nhiên n và m (1 ≤ n ≤ 25, 1 ≤ m ≤ 10⁹).

Kết quả: Ghi ra file CHUSO.OUT chữ số thứ m tìm được. Nếu không tìm được ghi −1.

Ví dụ:

CHUSO.INP	CHUSO.OUT
`123` `2 5`	`2`

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English