HSG lớp 9 Đồng Tháp 2015-2016

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐỒNG THÁP ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TỈNH Năm học 2015 - 2016
Đề thi môn Tin học - Ngày thi: 06/3/2016
Thời gian làm bài: 150 phút (không kể thời gian phát đề)
(Đề thi gồm có 02 trang)

---

Tổng quan bài thi

	Tên bài	Tệp chương trình	Dữ liệu vào	Kết quả ra
Bài 1	Teen	BL1.PAS	Từ bàn phím	Màn hình
Bài 2	Tàu cập cảng	BL2.PAS	TAUTHUY.INP	TAUTHUY.OUT
Bài 3	Sân điền kinh	BL3.PAS	DIENKINH.INP	DIENKINH.OUT

• Hạn chế kỹ thuật: Thời gian thực hiện chương trình không quá 1 giây.
• Giả thiết dữ liệu nhập vào là đúng đắn, thí sinh không cần kiểm tra.

Bài 1. Teen (6,0 điểm)

Bé Sen học rất giỏi môn tiếng Anh và bé rất thích từ TEEN. Khi gặp một xâu kí tự, bé Sen luôn tự hỏi từ các kí tự trong xâu đó có thể ghép được nhiều nhất bao nhiêu từ TEEN.

Yêu cầu: Cho trước xâu s nhập từ bàn phím. Xâu s chỉ gồm các chữ cái in hoa và kí tự trắng, có độ dài tối đa 255 kí tự. Xuất ra màn hình: số lượng kí tự T, số lượng kí tự E, số lượng kí tự N và số lượng từ TEEN nhiều nhất có thể tạo thành từ các kí tự của xâu s đã cho.

Ví dụ:

Nhập từ bàn phím	Xuất ra màn hình
CONNECT CONNECT EEET	T = 3 E = 5 N = 4 TEEN = 2

Bài 2. Tàu cập cảng (7,0 điểm)

Một công ty có hai tàu thủy chuyên vận chuyển hàng nông sản. Công ty rất uy tín với khách hàng nên hai tàu vận chuyển hàng hóa liên tục. Được uy tín như vậy là do tàu cập cảng luôn luôn đúng với số ngày quy định, vận chuyển an toàn và cập cảng ngày nào thì cũng rời cảng trong chính ngày đó. Tại cảng Đồng Tháp là nơi tàu nhận hàng, tàu thứ nhất cứ sau s ngày thì tàu cập cảng nhận hàng và tàu thứ hai cứ sau t ngày thì tàu cập cảng nhận hàng.

Yêu cầu: Nếu tại một thời điểm nào đó hai tàu nhận hàng rời cảng Đồng Tháp cùng lúc, thì sau n ngày hai tàu sẽ gặp lại nhau ở cảng Đồng Tháp bao nhiêu lần?

Dữ liệu vào: Cho từ tệp văn bản TAUTHUY.INP có định dạng:

• Dòng thứ nhất ghi số nguyên dương n (1 ≤ n ≤ 10⁹);
• Dòng thứ hai ghi hai số nguyên dương s, t (1 ≤ s, t ≤ 10⁴). Hai số ghi trên cùng một dòng cách nhau một ký tự trắng.

Kết quả: Ghi vào tệp văn bản TAUTHUY.OUT chỉ có một dòng ghi số nguyên là số lần hai tàu gặp nhau tại cảng Đồng Tháp.

Ví dụ:

TAUTHUY.INP	TAUTHUY.OUT
40 6 4	3

Ràng buộc dữ liệu:

• 60% số test tương ứng với 1 < n ≤ 10⁶
• 40% số test tương ứng với 10⁶ < n ≤ 10⁹

Bài 3. Sân điền kinh (7,0 điểm)

Trong một sân điền kinh, đầu sân là vạch sơn được đánh số 0 và người ta kẻ thêm n vạch sơn để thi đấu các cự ly khác nhau. Vạch sơn thứ 1 cách đầu sân a₁ mét, vạch sơn thứ 2 cách đầu sân a₂ mét, …, vạch sơn thứ n cách đầu sân aₙ mét (a₁ < a₂ < … < aₙ). Ban tổ chức cần tìm hai vạch sơn để thi đấu cự ly m mét.

Yêu cầu: Cho trước khoảng cách từ đầu sân đến n vạch sơn. Hãy tìm vạch sơn thứ x và vạch sơn thứ y để thi đấu cự ly m mét (tức a_y - a_x = m).

Dữ liệu vào: Cho từ tệp văn bản DIENKINH.INP có định dạng:

• Dòng thứ nhất ghi hai số nguyên dương n và m (1 ≤ n ≤ 10⁶, 1 ≤ m ≤ 10⁶);
• Dòng thứ hai ghi n số nguyên dương a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶, i = 1..n). Các số ghi trên cùng một dòng cách nhau một ký tự trắng.

Kết quả: Ghi vào tệp văn bản DIENKINH.OUT chỉ có một dòng, ghi hai số nguyên dương x, y tìm được. Nếu có nhiều đáp án thì ghi đáp án gần đầu sân nhất, nếu không có đáp án thì ghi số -1.

Ví dụ:

DIENKINH.INP	DIENKINH.OUT
4 6 1 5 7 11	1 3

Ràng buộc dữ liệu:

• 60% số test tương ứng với 1 < n ≤ 10³
• 40% số test tương ứng với 10³ < n ≤ 10⁶