HSG lớp 12 Nghệ An 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN ĐỀ CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 12 Năm học 2023 - 2024
Môn thi: Tin học
Thời gian làm bài: 150 phút (không kể thời gian giao đề)

---

Tổng quan bài thi

Tên bài	File nguồn	File Input	File Output	Bộ nhớ tối đa	Thời gian
ShenYun	ShenYun.*	ShenYun.Inp	ShenYun.Out	1024Mb	1 giây
Tên Gọi	TenGoi.*	TenGoi.Inp	TenGoi.Out	1024Mb	1 giây
Cuộc Thi	CuocThi.*	CuocThi.Inp	CuocThi.Out	1024Mb	1 giây
Trò Chơi	TroChoi.*	TroChoi.Inp	TroChoi.Out	1024Mb	1 giây

Phần mở rộng .* được thay thế bằng Cpp, Py ứng với các ngôn ngữ lập trình C++, Python.

Hãy lập trình giải các bài toán sau

Câu 1. (6 điểm) ShenYun

Đoàn nghệ thuật biểu diễn ShenYun là đoàn nghệ thuật đỉnh cao số một thế giới, lấy cảm hứng từ văn hóa truyền thống, cốt truyện xoay quanh những giá trị như Nhân, Lễ, Nghĩa, Trí, Tín. ShenYun làm hồi sinh các giá trị truyền thống, và là sự kết hợp tinh hoa của văn hóa nhân loại từ xưa đến nay. Với vũ đạo đẹp mắt, tươi vui, cùng phông nền 3D sống động đem lại cho người xem cảm xúc vui vẻ, yêu đời, yêu cuộc sống… Âm nhạc mỹ diệu của ShenYun chạm vào trái tim người nghe, làm thức dậy sự thiện lương tốt đẹp trong tâm hồn mỗi con người. Đặc biệt, khi một người nghe có tần số cảm nhận âm nhạc là x khi nghe một nốt nhạc có cao độ là bội của x thì người đó sẽ cảm thấy tâm hồn thư thái như hòa cùng thiên nhiên, giúp cân bằng âm dương và cơ thể khỏe mạnh hơn, nên nốt nhạc đó được gọi là nốt nhạc “hòa hợp” của người nghe đó.

An và Bình cùng nghe một bản nhạc giao hưởng của ShenYun, bản nhạc là một chuỗi N nốt nhạc phân biệt, có cao độ là một hoán vị của các số từ 1 đến N, cả hai sẽ rất vui thích khi gặp nốt nhạc cùng là nốt “hòa hợp” của cả hai. Cho trước N là số nốt nhạc của bản nhạc và x, y tương ứng là tần số cảm nhận âm nhạc của An và Bình.

Yêu cầu: Hãy cho biết trong bản nhạc có bao nhiêu nốt nhạc là nốt “hòa hợp” của cả An và Bình.

Dữ liệu vào từ tệp: ShenYun.inp

Chỉ một dòng duy nhất chứa 3 số nguyên dương N, x, y (1 ≤ N, x, y ≤ 10¹²)

Kết quả ghi ra tệp: ShenYun.out

Chỉ một số duy nhất là số lượng nốt nhạc “hòa hợp” của cả An và Bình.

Ví dụ:

ShenYun.inp	ShenYun.out	Giải thích
20 2 3	3	Từ 20 nốt nhạc có cao độ từ 1 đến 20 có 3 nốt nhạc “hòa hợp” của cả hai có cao độ là: 6, 12, 18

Giới hạn:

• Có 80% số điểm tương ứng với 1 ≤ N ≤ 10⁸;
• Có 20% số điểm tương ứng với 10⁸ < N ≤ 10¹²;

Câu 2. (5 điểm) Tên Gọi

Một bộ tộc nọ có rất nhiều ngôi làng, nhưng các ngôi làng lại chưa được đặt tên. Tộc trưởng muốn đặt tên cho các ngôi làng theo quy tắc:

• Dùng N xâu S₁, S₂, …, S_N để đặt tên (N ≤ 10⁴). Các xâu chỉ chứa các chữ cái tiếng Anh in hoa và không dài hơn 10⁴ ký tự.
• Tên của các ngôi làng là xâu con các ký tự liên tiếp trong các xâu S₁, S₂, …, S_N.
• Là một người yêu thích hòa bình và ghét chiến tranh, nên tộc trưởng muốn tên các ngôi làng không được có bất kỳ ký tự nào là ‘W’, ‘A’, ‘R’.

Yêu cầu: Trong tất cả các tên có thể đặt cho các ngôi làng, hãy đưa ra độ dài của tên dài nhất và số lượng các tên có cùng độ dài lớn nhất đó. Nếu trường hợp không tìm được tên nào thỏa mãn thì đưa ra là NO

Dữ liệu vào từ tệp: TenGoi.Inp

• Dòng 1 ghi số nguyên dương N, là số lượng xâu có thể dùng để đặt tên.
• N dòng tiếp theo, mỗi dòng ghi một xâu kí tự là S₁, S₂, …, S_N.

Kết quả ghi ra tệp: TenGoi.Out

Đưa ra 2 số là độ dài và số lượng các tên có cùng độ dài lớn nhất. Nếu không có tên nào thỏa mãn thì ghi là NO

Ví dụ:

TenGoi.Inp	TenGoi.Out	Giải thích
3 ABRBCDAB LCKHABWCHTHUR ABCKHTWE	5 2	Tên gọi thỏa mãn quy tắc và có độ dài lớn nhất là 2 xâu CHTHU, BCKHT có 5 ký tự.

Giới hạn: Gọi N là số lượng xâu, T là độ dài các xâu

• Có 60% số điểm tương ứng với 1 < N, T ≤ 10²;
• Có 20% số điểm tương ứng với 10² < N, T ≤ 10³;
• Có 20% số điểm tương ứng với 10³ < N, T ≤ 10⁴;

Câu 3. (5 điểm) Cuộc Thi

Cuộc thi chạy việt dã năm nay có nhiều vận động viên từ khắp nơi về tham dự. Để đảm bảo các vận động viên không bị lạc đường cũng như có sự hỗ trợ khi cần, ban tổ chức đã sắp xếp N tình nguyện viên tại các điểm khác nhau dọc con đường chạy thi. Để đảm bảo rằng các tình nguyện viên được sắp xếp cách nhau một cách hợp lý, ban tổ chức đưa ra Q câu hỏi, mỗi câu hỏi yêu cầu cho biết số tình nguyện viên trong một đoạn đường cho trước.

Dữ liệu vào từ tệp: CuocThi.Inp

• Dòng đầu chứa 2 số N và Q. (1 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵)
• Dòng thứ 2 chứa N số nguyên phân biệt: x₁, x₂, …, x_N, mỗi số thuộc đoạn 0…10⁹ cho biết vị trí một tình nguyện viên.
• Mỗi dòng trong Q dòng sau chứa 2 số nguyên A và B (0 ≤ A ≤ B ≤ 10⁹) ứng với câu hỏi cho biết có bao nhiêu tình nguyện viên trong đoạn từ A đến B.

Kết quả ghi ra tệp: CuocThi.Out

Đưa ra Q dòng, mỗi dòng là một số nguyên trả lời cho câu hỏi tương ứng

Ví dụ:

CuocThi.Inp	CuocThi.Out
4 6 3 2 7 5 2 3 2 4 2 5 2 7 4 6 8 10	2 2 3 4 1 0

Giới hạn:

• Có 50% số điểm tương ứng với N ≤ 10², Q ≤ 10³, 0 ≤ A ≤ B ≤ 10², 0 ≤ x_i ≤ 10⁵;
• Có 50% số điểm tương ứng với các trường hợp còn lại;

Câu 4. (4 điểm) Trò Chơi

Nhân kỷ niệm 50 năm ngày thành lập trường, có N học sinh đăng ký tham gia trò chơi “những người bạn vui vẻ”, N học sinh xếp thành một hàng đánh số từ 1 đến N, người thứ i có số hiệu là b_i. Cần chọn một nhóm liên tiếp có ít nhất 3 học sinh, nghĩa là cần chọn một nhóm các học sinh từ vị trí i đến vị trí j sao cho: 1 ≤ i < j ≤ N và j − i ≥ 2. Ban tổ chức sẽ đánh dấu 3 học sinh (bắt buộc có 1 học sinh ở đầu đoạn và 1 học sinh ở cuối đoạn) trong nhóm được chọn có vai trò lãnh đạo để tổ chức trò chơi cho nhóm mình, để tránh nhầm lẫn mỗi lãnh đạo phải có số hiệu khác với tất cả những người còn lại trong nhóm (làm lãnh đạo hoặc không).

Yêu cầu: Hãy tính xem có bao nhiêu cách chọn nhóm tham gia trò chơi. Hai cách chọn nhóm được xem là khác nhau nếu có số thành viên khác nhau hoặc lãnh đạo khác nhau.

Dữ liệu vào từ tệp: TroChoi.Inp

• Dòng đầu tiên chứa số N (1 < N < 2.10⁵)
• Dòng thứ 2 chứa N số b₁, b₂, …, b_N (1 ≤ b_i ≤ N)

Kết quả ghi ra tệp: TroChoi.Out

Chỉ một số duy nhất là số lượng cách tìm được

Ví dụ:

TroChoi.Inp	TroChoi.Out	Giải thích
7 1 2 3 4 3 2 5	9	Mỗi nhóm được chọn tương ứng với một bộ lãnh đạo sau: (1,2,3), (1,2,4), (1,3,4), (1,4,7), (2,3,4), (4,5,6), (4,5,7), (4,6,7), (5,6,7)

Giới hạn:

• Có 10% số điểm tương ứng với N < 50
• Có 10% số điểm tương ứng với 50 ≤ N < 500
• Có 20% số điểm tương ứng với 500 ≤ N < 5000
• Có 60% số điểm tương ứng với các trường hợp còn lại.