HSG lớp 9 Nam Định 2017-2018

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH NAM ĐỊNH Năm học 2017 - 2018

MÔN TIN HỌC 4 bài: CHUAN, DAYCON, BUS, GACH

---

Ghi chú

Đề được đánh máy lại theo tài liệu “50 đề thi HSG THCS” (không kèm phần tiêu đề, thời gian làm bài và thang điểm của đề gốc).

Bài 1. Xâu chuẩn

Cho xâu S chỉ gồm các dấu ngoặc ‘(’ và dấu ngoặc ‘)’ với độ dài tối đa 255 kí tự.

Xâu S được xác định là một xâu chuẩn nếu thỏa mãn các điều kiện sau:

• Số dấu ngoặc mở bằng số dấu ngoặc đóng.
• Nếu duyệt từ trái sang phải, số lượng dấu ngoặc mở luôn lớn hơn hoặc bằng số lượng dấu ngoặc đóng.

Ví dụ: Xâu (()(())) có cách đặt ngoặc đúng là xâu chuẩn. Xâu ()())) có cách đặt ngoặc không đúng là xâu không chuẩn.

Yêu cầu: Hãy viết chương trình kiểm tra xâu S có phải là xâu chuẩn hay không?

Dữ liệu: Vào từ tệp văn bản CHUAN.INP chứa xâu S chỉ gồm các dấu ngoặc.

Kết quả: Ghi ra tệp văn bản CHUAN.OUT có nội dung CHUAN hoặc KHONG tương ứng với dữ liệu vào.

Ví dụ:

CHUAN.INP	CHUAN.OUT	Chú thích
(()(()))	CHUAN	Kết quả phải ghi chữ in hoa
()()))	KHONG

Bài 2. Đoạn con dài nhất

Cho dãy N số nguyên (0 < N ≤ 10⁵) và số nguyên dương K.

Yêu cầu: Hãy tìm đoạn con dài nhất các phần tử liên tiếp nhau cùng chia hết cho K.

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

• Dòng thứ nhất ghi 2 số nguyên N và K cách nhau một dấu cách.
• Dòng thứ hai ghi N số nguyên dương aᵢ (aᵢ ≤ 10⁹, i ≤ N), mỗi số cách nhau một dấu cách.

Kết quả: Ghi ra tệp văn bản DAYCON.OUT gồm một số nguyên duy nhất là độ dài của đoạn con tìm được.

Ví dụ:

DAYCON.INP	DAYCON.OUT
4 6 6 14 6 24	2

Bài 3. Xe buýt

Trên những con đường nối liền các huyện, thành phố của tỉnh Nam Định, các chuyến xe buýt được tổ chức theo cách sau đây: Xe buýt có thể chạy không dừng theo các đoạn 1, 2, 3, …, 9 km. Với mỗi đoạn trong 9 đoạn này có giá vé cố định cho trong một bảng.

Ví dụ như bảng giá vé sau:

Độ dài đoạn đường đi	1 km	2 km	3 km	4 km	5 km	6 km	7 km	8 km	9 km
Giá vé	12	19	31	40	61	65	69	79	90

Một hành khách muốn đi N km bằng xe buýt (1 ≤ N ≤ 1000).

Yêu cầu: Hãy viết chương trình để hành khách có thể chọn những khoảng cách dừng xe hợp lý để hành trình phải trả tiền ít nhất.

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

• Dòng đầu tiên ghi số N.
• Dòng thứ hai ghi 9 số nguyên dương là giá tiền tương ứng của các đoạn 1, 2, …, 9 km.

Kết quả: Ghi ra tệp văn bản BUS.OUT gồm một số nguyên duy nhất là số tiền ít nhất phải trả.

Ví dụ:

BUS.INP	BUS.OUT
5 12 19 31 40 61 65 69 79 90	50

Bài 4. Xếp gạch

Có N đống gạch được xếp thành một hàng, đống thứ i có aᵢ viên gạch. Người ta có thể ghép hai đống gạch kề nhau thành một đống và mất một chi phí thời gian có giá trị bằng tổng số viên gạch của hai đống gạch đó (để ghép đống gạch thứ i thì mất aᵢ đơn vị thời gian).

Yêu cầu: Hãy viết chương trình để ghép N đống gạch trên thành một đống sao cho tổng thời gian là lớn nhất.

Dữ liệu: Vào từ tệp GACH.INP:

• Dòng đầu tiên ghi số N (1 < N ≤ 100) là số đống gạch.
• Dòng thứ hai ghi N số nguyên dương aᵢ, với aᵢ là số viên gạch của đống thứ i (aᵢ ≤ 1000; 1 ≤ i ≤ N).

Kết quả: Ghi ra tệp GACH.OUT gồm một số nguyên duy nhất là tổng thời gian lớn nhất tìm được.

Ví dụ:

GACH.INP	GACH.OUT	Chú thích cho ví dụ bên
4 5 2 8 3	43	Bước 1. Ghép đống 2 và đống 3: thời gian là 2 + 8 = 10 Bước 2. Ghép đống 1 và đống vừa ghép ở bước 1: thời gian là 5 + 10 = 15 Bước 3. Ghép đống ở bước 2 với đống còn lại: thời gian là 15 + 3 = 18 Tổng thời gian là: 10 + 15 + 18 = 43