HSG lớp 9 Đà Nẵng 2015-2016

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ ĐÀ NẴNG ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 Năm học 2015 - 2016
Môn thi: Tin học
Thời gian làm bài: 150 phút (không tính thời gian giao đề)

---

Tổng quan

	Tên bài	File chương trình	File dữ liệu vào	File dữ liệu ra
Bài 1	Chữ số 0 tận cùng	CHUSO1.*	CHUSO1.INP	CHUSO1.OUT
Bài 2	Trò chơi rải sỏi	RAISOI.*	RAISOI.INP	RAISOI.OUT
Bài 3	Phân nhóm	GROUP.*	GROUP.INP	GROUP.OUT

Bài 1. Chữ số 0 tận cùng (4 điểm)

Nhập vào một số nguyên dương N (với 2 ≤ N ≤ 100000). Gọi X là tích 1 · 2 · 3 · … · N.

Yêu cầu: Tìm số nguyên M là số lượng chữ số 0 tận cùng của số X.

Dữ liệu vào: Từ file văn bản CHUSO1.INP chứa một số nguyên dương N (với 2 ≤ N ≤ 100000).

Dữ liệu ra: Ghi ra file văn bản CHUSO1.OUT số nguyên M là số lượng chữ số 0 tận cùng của số X.

Ví dụ:

CHUSO1.INP	CHUSO1.OUT
5	1

Giải thích: N = 5 ta có X = 1 · 2 · 3 · 4 · 5 = 120 có 1 chữ số 0 tận cùng.

Bài 2. Trò chơi rải sỏi (3 điểm)

Trò chơi rải sỏi là một trò chơi khá đơn giản nhưng thú vị, đòi hỏi người chơi cần phải tính toán hợp lí sao cho mỗi lần chơi được kết quả tốt nhất. Trò chơi được mô tả như sau:

Vật dụng cho trò chơi gồm:

• Một bàn cờ có hình vành khăn, mà trên đó người ta đã chia thành N ô nhỏ bằng nhau, các ô được đánh số liên tục từ 1 đến N theo chiều kim đồng hồ.
• Một số ô đã rải sẵn một số viên sỏi.

Ở hình minh họa, ta có bàn cờ được chia thành 6 ô nhỏ bằng nhau tương ứng với N = 6.

Cách chơi:

Người chơi chọn một ô bất kì có chứa sỏi và lấy hết số sỏi này, sau đó chọn cho mình một chiều đi theo chiều kim đồng hồ hoặc ngược lại và suốt một lượt chơi chỉ đi theo chiều này.

Một lượt chơi gồm 2 bước sau:

• Bước 1: Theo chiều đã chọn, qua mỗi ô rải một viên sỏi bắt đầu từ ô liền kề với ô đã chọn, cứ làm như vậy cho đến hết số viên sỏi đã lấy ra. Gọi ô cuối cùng được rải một viên sỏi vào là ô thứ K.
• Bước 2: Người chơi lấy hết các viên sỏi ở ô kề với ô thứ K (theo chiều đã chọn) và dừng lượt chơi.

Yêu cầu: Nếu là người chơi thì với một lượt chơi bạn có thể kiếm được tối đa bao nhiêu viên sỏi?

Dữ liệu vào: Từ file văn bản RAISOI.INP có cấu trúc như sau:

• Dòng đầu tiên ghi số nguyên dương N (N ≤ 100).
• Dòng tiếp theo ghi N số nguyên không âm mà số thứ i chính là số viên sỏi đã rải sẵn ở ô thứ i trong bàn cờ (mỗi số cách nhau ít nhất 1 dấu cách). Số sỏi ở mỗi ô trong N ô này đều không vượt quá 10¹² viên.

Dữ liệu ra: Ghi ra file văn bản RAISOI.OUT một số nguyên M là số viên sỏi nhiều nhất có thể lấy ra được trong một lượt chơi.

Ví dụ:

RAISOI.INP	RAISOI.OUT
6 0 3 0 1 4 2	3

Giải thích: Chọn ô thứ 4 và đi theo chiều ngược chiều kim đồng hồ thì được 3 viên sỏi.

Bài 3. Phân nhóm (3 điểm)

Phân tích nhóm (phân nhóm, chia nhóm) là công việc phân chia các phần tử trong một tập hợp thành một hoặc nhiều nhóm mà trong đó, các phần tử trong cùng một nhóm sẽ giống nhau hơn so với phần tử thuộc nhóm khác.

Yêu cầu: Cho một tập N số nguyên dương và một số nguyên dương K, nhiệm vụ của bạn là đếm xem có bao nhiêu nhóm. Biết rằng 2 phần tử được xếp chung nhóm với nhau nếu như chênh lệch giữa chúng không vượt quá K.

Giải thích: Với tập N = 7 số nguyên dương: 2, 6, 1, 7, 3, 4, 9 và K = 1 thì ta sẽ có các mối quan hệ sau:

• 2 và 1 chung một nhóm (chênh lệch giữa chúng là 1, không vượt quá K)
• 2 và 3 chung một nhóm
• 6 và 7 chung một nhóm
• 3 và 4 chung một nhóm

Vậy ta sẽ có 3 nhóm: (1, 2, 3, 4), (6, 7) và (9).

Dữ liệu vào: Từ file văn bản GROUP.INP:

• Dòng đầu tiên chứa số nguyên T - là số bộ test cần kiểm tra (T ≤ 20).
• Các dòng tiếp theo chứa T bộ test, mỗi bộ test gồm 2 dòng:
  • Dòng đầu trong mỗi bộ test chứa 2 số nguyên dương N, K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10⁶) cách nhau ít nhất 1 dấu cách.
  • Dòng thứ hai trong mỗi bộ test chứa N số nguyên dương - là các phần tử của tập hợp (giá trị không vượt quá 10⁶).

Dữ liệu ra: Ghi ra file văn bản GROUP.OUT gồm T dòng, mỗi dòng chứa một số nguyên dương là số nhóm tương ứng của mỗi bộ test.

Ví dụ:

GROUP.INP	GROUP.OUT
3 7 1 2 6 1 7 3 4 9 7 2 2 6 1 7 3 4 9 5 5 15 1 20 4 17	3 1 2

---

• Thí sinh không được sử dụng tài liệu.
• Cán bộ coi thi không giải thích gì thêm.