HSG lớp 9 Hà Nội 2021-2022

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI Năm học 2021 - 2022

KÌ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP THÀNH PHỐ Môn thi: Tin học
5 bài: DRB, ARN, TBG, HCN, VNI

---

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. Đua robot

Có hai robot đang chuyển động thẳng đều, cùng chiều trên cùng một con đường, robot thứ nhất đang ở vị trí S₁ di chuyển với vận tốc là V₁ m/s, robot thứ hai đang ở vị trí S₂ di chuyển với vận tốc là V₂ m/s. Hỏi sau bao nhiêu lâu thì hai robot gặp nhau?

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

• Dòng đầu tiên gồm số nguyên dương S₁ mô tả vị trí của robot thứ nhất;
• Dòng thứ hai gồm số nguyên dương V₁ mô tả vận tốc của robot thứ nhất;
• Dòng thứ ba gồm số nguyên dương S₂ mô tả vị trí của robot thứ hai;
• Dòng thứ tư gồm số nguyên dương V₂ mô tả vận tốc của robot thứ hai.
• Các đơn vị khoảng cách được tính bằng mét, thời gian được tính bằng giây và S₁ ≠ S₂; S₁, S₂, V₁, V₂ ≤ 10⁹.

Kết quả: ghi ra file văn bản DRB.OUT: một số nguyên là phần nguyên của kết quả - thời gian mà hai robot gặp nhau. Nếu hai robot không thể gặp nhau thì in ra −1.

Ví dụ:

DRB.INP	DRB.OUT	Giải thích
2 5 7 3	2	Sau 2.5 giây hai robot sẽ gặp nhau: 2 + 5 × 2.5 = 14.5 7 + 3 × 2.5 = 14.5 Phần nguyên của 2.5 là 2.
2 3 7 5	-1	Hai robot càng đi càng xa nhau.

Bài 2. Chuỗi ARN

Trong phòng thí nghiệm, các nhà khoa học đang nghiên cứu về gen của một chuỗi ARN đặc biệt được mã hoá bằng một xâu S gồm các kí tự ‘A’, ‘U’, ‘G’, ‘X’. Họ muốn cắt từ chuỗi ARN đó một mạch (được mã hoá bằng xâu X) cho trước.

Yêu cầu: từ chuỗi ARN S có thể cắt được ra tối đa bao nhiêu đoạn mạch X.

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

• Dòng đầu tiên gồm một xâu kí tự S mô tả chuỗi ARN;
• Dòng thứ hai gồm một xâu kí tự X mô tả đoạn mạch cần cắt ra.
• Các xâu chỉ gồm các kí tự ‘A’, ‘U’, ‘G’, ‘X’ và độ dài các xâu không quá 10³ kí tự.

Kết quả: ghi ra file văn bản ARN.OUT: một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

ARN.INP	ARN.OUT	Giải thích
AUAUGXXAUGXGX AUGX	2	AUAUGXXAUGXGX
AAAAA AAA	1	AAAAA
AGAX U	0

Bài 3. Tải bài giảng

Do ảnh hưởng của dịch bệnh, các lớp học sẽ học kết hợp cả hình thức trực tiếp và trực tuyến. Để học sinh có thể hiểu kĩ hơn về bài học, giáo viên lưu lại video các bài giảng và tải lên nhóm lớp cho học sinh xem lại.

Một video bài giảng dài Z giây. Dung lượng mà video cần phát 1 giây là X MB. Nhưng mạng nhà An lúc đó chỉ có thể tải được Y MB trong 1 giây.

An muốn xem bài giảng mà không phải dừng lại giữa chừng. An quyết định trước khi bắt đầu xem, sẽ đợi trước T₀ giây để bài giảng được tải xuống một dung lượng nhất định. Một video bài giảng được phát liên tục nếu tổng dung lượng tại thời điểm bất kì mà An đã tải về lớn hơn hoặc bằng tổng dung lượng của đoạn video tính đến thời điểm đó.

Yêu cầu: Hãy giúp An tìm lượng thời gian ít nhất T₀ mà An phải đợi để có thể xem liên tục.

Dữ liệu vào: từ file văn bản TBG.INP: gồm một dòng chứa ba số nguyên dương X, Y, Z (1 ≤ X, Y, Z ≤ 10⁵; Y < X).

Kết quả: ghi ra file văn bản TBG.OUT: một số nguyên dương T₀ là thời gian ít nhất mà An phải đợi.

Ràng buộc:

• Có 80% số test ứng với 80% số điểm của bài thoả mãn: 1 ≤ X, Y, Z ≤ 100;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

TBG.INP	TBG.OUT	Giải thích
4 1 1	3	- An đợi trước 3 giây nên An đã tải được sẵn 3 × 1 = 3 MB. - Tại giây thứ nhất của video, dung lượng mà An tải được sẽ là 3 + 1 = 4 MB, vừa bằng dung lượng mà video phát trong 1 giây là 4 MB.
10 3 2	5	- An đợi trước 5 giây nên An đã tải được sẵn 5 × 3 = 15 MB. - Tại giây thứ nhất của video, dung lượng mà An tải được sẽ là 15 + 3 = 18 MB. Lớn hơn dung lượng mà video phát trong 1 giây là 10 MB. - Tại giây thứ 2 của video, dung lượng mà An tải được sẽ là 18 + 3 = 21 MB. Lớn hơn dung lượng mà video phát trong 2 giây là 20 MB.

Bài 4. Hình chữ nhật

Cho một hình chữ nhật gồm N dòng và M cột. Các dòng được đánh số từ 1 đến N, từ trên xuống dưới. Các cột được đánh số từ 1 đến M, từ trái sang phải. Ô ở dòng thứ i và cột thứ j được gọi là ô (i, j) và có diện tích là 1 đơn vị. Có một số ô đã được điền sẵn kí tự ‘X’.

Yêu cầu: tìm hình chữ nhật con có diện tích lớn nhất chỉ chứa duy nhất một kí tự ‘X’.

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

• Dòng đầu tiên gồm ba số nguyên dương N, M, K (N, M ≤ 10⁴; K ≤ 10³) mô tả kích thước của hình chữ nhật và số lượng kí tự ‘X’ có trong hình chữ nhật;
• K dòng sau, mỗi dòng gồm hai số nguyên dương d và c là chỉ số dòng và cột của ô điền kí tự ‘X’ (d ≤ N; c ≤ M).

Kết quả: ghi ra file văn bản HCN.OUT: diện tích của hình chữ nhật lớn nhất thoả mãn yêu cầu đề bài.

Ràng buộc:

• Có 50% số test tương ứng với 50% số điểm thoả mãn: N, M ≤ 50;
• 30% số test khác tương ứng với 30% số điểm thoả mãn: N, M ≤ 500;
• 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Ví dụ:

HCN.INP	HCN.OUT
4 5 4 2 3 2 5 3 1 4 4	9

Giải thích:

Bài 5. Cổ phiếu VNI

Bình mua bán cổ phiếu VNI trên thị trường chứng khoán. Giả sử giá của một cổ phiếu VNI trong vòng N ngày lần lượt là A₁, A₂, …, A_N. Biết rằng mỗi ngày Bình chỉ thực hiện một trong những hoạt động sau:

1. Mua một cổ phiếu VNI;
2. Bán số lượng cổ phiếu VNI bất kì mà Bình đang sở hữu;
3. Không thực hiện bất kì giao dịch nào.

Yêu cầu: Bình thực hiện mua bán cổ phiếu VNI như thế nào để thu được lợi nhuận lớn nhất nếu anh ấy tham gia mua bán bắt đầu từ ngày thứ T cho trước?

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

• Dòng đầu tiên gồm số nguyên dương N (N ≤ 10⁵) là số ngày biết giá cổ phiếu;
• Dòng thứ hai gồm N số nguyên dương A₁, A₂, …, A_N tương ứng là giá của một cổ phiếu VNI trong từng ngày (Aᵢ ≤ 10⁹; 1 ≤ i ≤ N);
• Dòng thứ ba gồm một số nguyên dương Q là số lượng truy vấn (Q ≤ 10⁵);
• Q dòng sau, mỗi dòng gồm một số nguyên dương T (T ≤ N) thể hiện cho ngày đầu tiên mà Bình tham gia việc mua bán cổ phiếu VNI.

Kết quả: ghi ra file văn bản VNI.OUT: Q dòng, mỗi dòng gồm một số nguyên duy nhất là lợi nhuận lớn nhất mà Bình thu được ở mỗi truy vấn tương ứng.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm của bài thoả mãn: N ≤ 1000; Q = 1;
• 30% số test khác ứng với 30% số điểm của bài thoả mãn: N ≤ 10⁵; Q = 1;
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

VNI.INP	VNI.OUT	Giải thích
4 1 2 5 4 2 1 3	7 0	Bình bắt đầu tham gia mua bán VNI vào ngày 1: - Ngày 1: mua 1 VNI với giá là 1. - Ngày 2: mua 1 VNI với giá là 2. - Ngày 3: bán 2 VNI với giá là 5. - Ngày 4: không mua hay bán VNI vào ngày này. ⇒ Lợi nhuận thu được là: −1 − 2 + 2 × 5 = 7. Bình bắt đầu tham gia mua bán VNI vào ngày 3: - Bình không mua bán VNI vào ngày 3 và ngày 4. ⇒ Lợi nhuận thu được là: 0.