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

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 2014 - 2015
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	Dãy số	SEQ.*	SEQ.INP	SEQ.OUT
Bài 2	Xâu tiền tố dài nhất	LPREFIX.*	LPREFIX.INP	LPREFIX.OUT
Bài 3	Sinh số	NUMSPLIT.*	NUMSPLIT.INP	NUMSPLIT.OUT

Bài 1. Dãy số

Cho một dãy gồm n số nguyên a₁, a₂, a₃, …, aₙ (n ∈ ℕ; n ≥ 2).

Yêu cầu: Hãy tìm trong dãy số trên một số nguyên bằng tổng tất cả các số nguyên còn lại.

Dữ liệu: Vào từ file văn bản SEQ.INP:

• Dòng thứ nhất ghi một số nguyên dương n (2 ≤ n ≤ 200).
• Dòng thứ hai ghi n số nguyên a₁, a₂, a₃, …, aₙ, các số cách nhau ít nhất một dấu cách. Biết rằng |aᵢ| ≤ 10⁹ với mọi số nguyên i thỏa mãn 1 ≤ i ≤ n.

Kết quả: Ghi ra file văn bản SEQ.OUT một số nguyên tìm được trong dãy số đã cho thỏa mãn yêu cầu đề bài. Trường hợp không có số nào trong dãy thỏa mãn yêu cầu đề bài thì ghi một kí tự “N”.

Ví dụ:

SEQ.INP	SEQ.OUT
4 -2 5 3 6	6
3 2 3 4	N

Bài 2. Xâu tiền tố dài nhất

Xâu A được gọi là tiền tố của xâu B nếu length(A) ≤ length(B) và sau khi ta xóa đi một số kí tự cuối cùng của B thì thu được xâu A.

Yêu cầu: Cho N xâu, bạn hãy tìm một xâu dài nhất sao cho nó là tiền tố của ít nhất 2 trong số N xâu đã cho. Nếu có nhiều xâu thỏa mãn có cùng độ dài, hãy đưa ra đáp án xuất hiện đầu tiên theo thứ tự từ điển.

Dữ liệu: Vào từ file văn bản LPREFIX.INP:

• Dòng thứ nhất ghi số nguyên dương N (2 ≤ N ≤ 5000).
• Dòng thứ i trong N dòng tiếp theo ghi xâu Wᵢ (2 ≤ length(Wᵢ) ≤ 100).

Kết quả: Ghi ra file văn bản LPREFIX.OUT một dòng duy nhất ghi xâu tiền tố dài nhất thỏa mãn yêu cầu đề bài.

Ví dụ:

LPREFIX.INP	LPREFIX.OUT
7 CHEDDAR CHESSO CHAOURCE PARMESAN CHAUMES ROQUEFORT POSSIA	CHA

Giải thích: Các xâu là tiền tố của ít nhất 2 xâu là C, CH, CHA, CHE, P. Xâu dài nhất là xâu CHA và CHE nhưng xâu CHA xuất hiện trước CHE trong thứ tự từ điển.

Bài 3. Sinh số

Cho số nguyên dương N (0 ≤ N ≤ 10¹⁵).

Yêu cầu: Tìm số nguyên dương Q nhỏ nhất sao cho tích các chữ số của Q bằng N.

Dữ liệu: Vào từ file văn bản NUMSPLIT.INP:

• Dòng thứ nhất ghi số nguyên dương T (2 ≤ T ≤ 100) là số lượng test.
• T dòng tiếp theo, mỗi dòng ghi một số nguyên dương N.

Kết quả: Ghi ra file văn bản NUMSPLIT.OUT gồm T dòng, mỗi dòng ghi ra số Q tìm được tương ứng với số N, nếu không tìm được thì ghi ra số -1.

Ví dụ:

NUMSPLIT.INP	NUMSPLIT.OUT
3 10 16 13	25 28 -1

---

• 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.