HSG lớp 9 Kon Tum 2020-2021

ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 9 TỈNH KON TUM Năm học 2020 - 2021

MÔN TIN HỌC 4 bài: KCACH, PT, QUANGCAO, SMAX

---

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. Khoảng cách

Cho số nguyên dương n và dãy số nguyên a₁, a₂, …, aₙ. Ta định nghĩa khoảng cách giữa hai số đứng ở vị trí i và j là |aᵢ − aⱼ|.

Yêu cầu: Tìm cặp chỉ số i và j sao cho khoảng cách của chúng là lớn nhất có thể.

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

• Dòng 1: Chứa số nguyên dương n (2 ≤ n ≤ 10⁶).
• Dòng 2: Chứa n số nguyên a₁, a₂, …, aₙ (|aᵢ| ≤ 10⁶, i = 1..n).

Kết quả: Ghi ra file văn bản KCACH.OUT hai số nguyên i, j (i < j) tìm được trên một dòng, các số cách nhau một dấu cách. Nếu có nhiều cặp số thỏa mãn thì in ra cặp có chỉ số nhỏ nhất.

Ví dụ:

KCACH.INP	KCACH.OUT
6 2 1 4 6 5 6	2 4

Ràng buộc:

• 60% số test ứng với 60% điểm của bài thỏa mãn điều kiện 2 ≤ n ≤ 10³;
• 40% số test ứng với 40% điểm của bài thỏa mãn điều kiện 10³ < n ≤ 10⁶.

Bài 2. Phần thưởng

Trong cuộc thi năng khiếu môn Tin học do Sở Giáo dục và Đào tạo tổ chức, mỗi học sinh dự thi đều có số điểm thi tích lũy riêng của mình. Số điểm tích lũy của mỗi học sinh là một số nguyên dương V. Đội tuyển của trường THCS Năng Khiếu có N học sinh tham gia dự thi. Tại buổi gặp mặt trước kỳ thi cấp tỉnh, thầy Hiệu trưởng mong muốn tặng thưởng cho các học sinh K triệu đồng; tuy nhiên, thầy vẫn còn phân vân và mong muốn các em học sinh giúp thầy đưa ra số nguyên dương K lớn nhất thoả mãn điều kiện điểm tích lũy của mỗi học sinh đều chia hết cho K.

Yêu cầu: Em được cho biết điểm tích lũy của N học sinh, tìm K lớn nhất thỏa mãn điều kiện bài toán.

Dữ liệu: Vào từ file văn bản PT.INP có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương N là số lượng học sinh (2 ≤ N ≤ 100).
• Dòng 2: Ghi N số nguyên dương lần lượt là điểm tích lũy của N học sinh, các số nguyên dương và không vượt quá 10⁶, các số cách nhau ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản PT.OUT một số nguyên dương K tìm được.

Ví dụ:

PT.INP	PT.OUT
5 15 24 45 36 27	3

Bài 3. Biển quảng cáo

Theo xu hướng hiện nay, nhiều cửa hàng, doanh nghiệp đều sử dụng loại biển quảng cáo led chữ chạy để quảng bá cho thương hiệu sản phẩm của mình. Mặc dù giá cả làm biển quảng cáo led chữ chạy có phần cao hơn các loại biển quảng cáo khác. Nhưng chất lượng và hiệu quả quảng cáo mà nó mang lại thì không thể phủ nhận được. Chính vì vậy mà loại biển quảng cáo này vẫn giành được ưu thế thượng phong trên thị trường. Được nhiều khách hàng lựa chọn.

Nam đang thiết kế biển quảng cáo led chạy chữ theo yêu cầu của khách hàng như sau: Biển quảng cáo chạy chữ chỉ gồm 1 hàng và có độ dài đúng N kí tự. Xâu kí tự chạy trên bảng quảng cáo được cho trong xâu S có đúng N kí tự. Nam thiết kế dòng chữ chạy từ phải sang trái bảng theo quy tắc vòng tròn sau: Ban đầu bảng quảng cáo chưa có kí tự nào, mỗi giây các kí tự dịch chuyển qua trái 1 đơn vị và lần lượt xuất hiện trên bảng quảng cáo. Như vậy ở giây thứ nhất, kí tự đầu tiên trong xâu S xuất hiện trên bảng; ở giây thứ 2, kí tự thứ nhất và thứ 2 trong xâu S xuất hiện trên bảng, …, đến giây thứ N, tất cả N kí tự xuất hiện trên bảng; sau khi kí tự cuối cùng của xâu S xuất hiện trên bảng thì tiếp tục quay lại kí tự đầu tiên và cứ tiếp tục như vậy.

Ví dụ: với N = 5, xâu S = “ABCDE”, thì kết quả khi chạy bảng quảng cáo như sau:

Thời gian (giây)	Kết quả xuất hiện trên biển quảng cáo
1	A
2	AB
3	ABC
4	ABCD
5	ABCDE
6	BCDEA
7	CDEAB
…

Nam có một câu hỏi muốn đố các bạn nhỏ yêu thích lập trình đó là: Với hệ thống thiết kế của Nam thì ở thời điểm T trên bảng quảng cáo hiển thị những gì? Các bạn hãy trả lời câu hỏi của Nam nhé.

Yêu cầu: Em được cho biết N, xâu S và số nguyên dương T. Hãy cho biết dòng chữ hiển thị trên bảng quảng cáo ở giây thứ T.

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

• Dòng 1: Chứa hai số nguyên dương N, T (1 ≤ N ≤ 10⁶; 1 ≤ T ≤ 10⁹).
• Dòng 2: Chứa xâu S có độ dài đúng N kí tự thuộc bảng chữ cái Latinh in hoa.

Kết quả: Ghi ra file văn bản QUANGCAO.OUT dòng chữ hiển thị trên bảng quảng cáo ở thời điểm T theo thứ tự xuất hiện trên bảng từ trái qua phải.

Ví dụ:

QUANGCAO.INP	QUANGCAO.OUT
5 8 ABCDE	DEABC

Bài 4. Tổng lớn nhất

Từ khi An cài được phần mềm học tiếng anh với mật khẩu tìm được từ dãy số mà nhà sản xuất đã tặng, An rất thích thú với dãy số đã cho. Một hôm, An đến nhà Lâm chơi và kể cho Lâm nghe về việc được tặng một dãy số mật khẩu, nhìn thấy dãy số An nảy sinh ý tưởng và rủ Lâm chơi trò chơi tìm số. Hai bạn lần lượt mỗi người viết một số nguyên lên giấy roki, An viết số thứ nhất, Lâm viết số thứ hai, rồi đến lượt An viết số thứ ba, … Cứ tiếp tục như vậy hai bạn viết được một dãy gồm n số a₁, a₂, …, aₙ. Đến đây hai bạn chưa kịp chơi trò chơi của mình thì bố của Lâm đi làm về, Bố của Lâm cũng là một giáo viên dạy môn toán cấp 2. Ông tiến lại gần, sẵn thấy dãy số ghi trên giấy, ông đã đặt ra câu đố và sẵn sàng trao thưởng nếu ai tìm ra được đáp án đúng, câu đố như sau: Tìm một đoạn liên tiếp các số trong dãy số trên sao cho tổng giá trị các số trong đoạn đó là lớn nhất. Vì dãy số có quá nhiều số nên cả hai bạn nhìn hoa cả mắt mà vẫn chưa tìm ra được đáp án. Bạn hãy lập trình giải giúp hai bạn nhé.

Yêu cầu: Em được cho biết n và dãy a₁, a₂, …, aₙ. Tìm dãy số liên tiếp có tổng lớn nhất trong dãy a₁, a₂, …, aₙ.

Dữ liệu: Vào từ file văn bản có tên SMAX.INP có dạng như sau:

• Dòng đầu tiên ghi số nguyên n (1 ≤ n ≤ 10⁶).
• Dòng thứ hai ghi dãy n số nguyên a₁, a₂, …, aₙ (−1000 ≤ aᵢ ≤ 1000, i = 1..n).

Kết quả: Ghi ra file văn bản SMAX.OUT gồm một số nguyên duy nhất là tổng lớn nhất của một đoạn liên tiếp các số trong dãy tìm được.

Ví dụ:

SMAX.INP	SMAX.OUT
10 2 -9 4 1 -3 5 8 -7 3 1	15

(Đoạn có tổng lớn nhất là 4 1 −3 5 8.)

Ràng buộc:

• Có 40% test ứng với 40% điểm của bài có 1 ≤ n ≤ 10²;
• Có 30% test ứng với 30% điểm của bài có 10² < n ≤ 10³;
• Có 30% test ứng với 30% điểm của bài có 10³ < n ≤ 10⁶.