HSG lớp 9 Bà Rịa - Vũng Tàu 2018-2019

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH BÀ RỊA - VŨNG TÀU ĐỀ THI CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 THCS Năm học 2018 - 2019
Môn thi: Tin học - Ngày thi: 19/03/2019
Thời gian làm bài thi: 150 phút
(Đề thi có 2 trang)

---

Bài 1. Giá trị của biểu thức (8 điểm)

Tên file chương trình: FRACTION.PAS

Cho biểu thức:

A = x/y - 1/(1·2) + 1/(2·3) + ... + 1/(n·(n+1))

Yêu cầu: Hãy tính giá trị của biểu thức A và biến đổi đưa về phân số tối giản.

Dữ liệu vào từ file FRACTION.INP gồm dòng duy nhất ghi lần lượt 3 số nguyên x, y, n (0 < x, y ≤ 10⁶; 0 < n ≤ 10⁶).

Kết quả ghi vào file FRACTION.OUT hai số nguyên lần lượt là tử số và mẫu số của phân số tối giản tìm được theo yêu cầu.

Ví dụ:

FRACTION.INP	FRACTION.OUT
149 100 99	1 2

Ghi chú

Theo ví dụ, dấu trừ áp dụng cho cả tổng phía sau: A = x/y − (1/(1·2) + 1/(2·3) + … + 1/(n·(n+1))). Với x = 149, y = 100, n = 99: A = 149/100 − 99/100 = 1/2.

Bài 2. Dãy con tăng (7 điểm)

Tên file chương trình: ARRINC.PAS

Cho dãy số nguyên gồm n phần tử a₁, a₂, …, aₙ. Người ta muốn chọn ra các dãy con thỏa mãn tất cả các điều kiện sau:

• Phần tử được chọn trước phải có số thứ tự nhỏ hơn phần tử được chọn sau.
• Phần tử được chọn trước phải có giá trị nhỏ hơn phần tử được chọn sau.
• Dãy con phải có ít nhất hai phần tử.

Ví dụ: Dãy số có 5 phần tử tương ứng với các giá trị 3 2 11 4 5 → có 9 dãy con thỏa mãn tất cả các điều kiện trên: (3, 11); (3, 4); (3, 5); (2, 11); (2, 4); (2, 5); (4, 5); (3, 4, 5); (2, 4, 5).

Yêu cầu: Hãy cho biết có bao nhiêu dãy con thỏa mãn tất cả các điều kiện trên?

Dữ liệu: vào từ file ARRINC.INP:

• Dòng đầu tiên chứa số nguyên dương n (n ≤ 30).
• Trong n dòng sau, dòng thứ i là giá trị aᵢ (i = 1, 2, …, n; |aᵢ| ≤ 10⁹).

Kết quả: ghi vào file ARRINC.OUT một số nguyên là số dãy con thỏa mãn tất cả các yêu cầu.

Ví dụ:

ARRINC.INP	ARRINC.OUT
5 3 2 11 4 5	9

Bài 3. Xây cầu (5 điểm)

Tên file chương trình: BRIDGE.PAS

Ngày xưa hai đất nước Alpha và Beta nằm dọc ở hai bên bờ sông Omega (được xem như một đường thẳng). Đất nước Alpha thơ mộng có N thành phố được đánh số từ 1 đến N, thành phố thứ i có chỉ số thơ mộng là một số nguyên dương aᵢ. Đất nước Beta xinh đẹp có M thành phố được đánh số từ 1 đến M, thành phố thứ j có chỉ số xinh đẹp là một số nguyên dương bⱼ. Để tăng cường tình hữu nghị giữa hai nước người ta cho xây những cây cầu bắc qua hai bờ sông. Mỗi cây cầu sẽ là nhịp cầu nối hai thành phố kết nghĩa có chỉ số thơ mộng và xinh đẹp bằng nhau. Với yêu cầu là các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu.

Yêu cầu: Hãy cho biết có thể xây được nhiều nhất bao nhiêu cây cầu.

Dữ liệu vào: File BRIDGE.INP có nội dung như sau:

• Dòng thứ nhất chứa số nguyên dương N (N ≤ 10⁵).
• Dòng thứ hai chứa các số nguyên dương aᵢ (aᵢ ≤ 10⁹) là chỉ số thơ mộng của các thành phố nước Alpha.
• Dòng thứ ba chứa số nguyên dương M (M ≤ 10⁵).
• Dòng thứ tư chứa các số nguyên dương bⱼ (bⱼ ≤ 10⁹) là chỉ số xinh đẹp của các thành phố nước Beta.

Kết quả: Ghi vào file BRIDGE.OUT số cây cầu nhiều nhất có thể xây được.

Ví dụ:

BRIDGE.INP	BRIDGE.OUT
5 6 1 4 9 8 4 1 4 5 7	2