HSG lớp 12 Quảng Ngãi 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO QUẢNG NGÃI ĐỀ CHÍNH THỨC
(Đề thi gồm có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 12 Năm học 2024-2025
Ngày thi: 11/12/2024
Môn thi: Tin học
Thời gian làm bài: 180 phút

---

Tổng quan đề thi

Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả
Bài 1	BAI1.*	BAI1.INP	BAI1.OUT
Bài 2	BAI2.*	BAI2.INP	BAI2.OUT
Bài 3	BAI3.*	BAI3.INP	BAI3.OUT
Bài 4	BAI4.*	BAI4.INP	BAI4.OUT

Dấu * là CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C++ hoặc Python.

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

Bài 1 (4,0 điểm)

Phép nén của một số nguyên dương q là gán số đó thành số nguyên dương nhỏ nhất mà q không chia hết. Độ nén của một số nguyên dương là số lượng phép nén để số đó thành số 2.

Ví dụ: q = 4 thì độ nén của 4 là 2.

Giải thích:

• Phép nén của số 4 là 3, vì 3 là số nguyên dương nhỏ nhất mà 4 không chia hết;
• Phép nén của số 3 là 2 vì 2 là số nguyên dương nhỏ nhất mà 3 không chia hết.

Yêu cầu: Cho hai số nguyên dương m, n (2 ≤ m ≤ n < 10¹⁸). Hãy tính tổng độ nén của các số lớn hơn hoặc bằng m và nhỏ hơn hoặc bằng n.

Dữ liệu vào từ tệp văn bản BAI1.INP có cấu trúc:

• Một dòng duy nhất chứa hai số m và n.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI1.OUT có cấu trúc:

Một số nguyên là kết quả của bài toán.

Ví dụ:

BAI1.INP	BAI1.OUT	Giải thích
4 6	6	Độ nén của 4 là 2; Độ nén của 5 là 1; Độ nén của 6 là 3; Tổng độ nén là: 6.

Chú ý: Có 50% số test với n < 10⁶.

Bài 2 (6,0 điểm)

Mật khẩu là xâu kí tự có độ dài lớn hơn 0, phân biệt chữ hoa chữ thường và không chứa dấu cách. Từ mật khẩu ban đầu ta có thể tạo ra nhiều mật khẩu bằng cách hoán vị các kí tự của nó.

Yêu cầu: Tính số lượng mật khẩu khác nhau được tạo thêm từ mật khẩu đã cho.

Dữ liệu vào từ tệp văn bản BAI2.INP có cấu trúc:

• Dòng đầu tiên ghi số nguyên n là số lượng mật khẩu (0 < n ≤ 10³).
• n dòng tiếp theo, mỗi dòng là một mật khẩu có độ dài không quá 20 kí tự.

Kết quả ghi ra là tệp văn bản BAI2.OUT có cấu trúc:

Gồm n dòng, mỗi dòng ghi một số nguyên là phần dư của kết quả tính được với mật khẩu tương ứng chia cho 10⁹.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
2 Aab AAb	5 2	Các mật khẩu được tạo thêm từ: - Aab: Aba, aAb, abA, bAa, baA - AAb: AbA, bAA

Chú ý: Có 50% số test với n ≤ 100.

Bài 3 (5,0 điểm)

Trong cuộc chiến giữa hai bên, Đô đốc Salem nhận thấy quân địch đang trong tình trạng suy kiệt cả về số lượng lẫn chất lượng, nên ông đã gấp rút chuẩn bị quân đội để phản công dành chiến thắng. Quân đội của ông có n người lính, mỗi người lính trong hàng ngũ đều có một chỉ số riêng biệt. Dãy chỉ số của n người lính là một hoán vị của dãy số nguyên từ 1 đến n. Để đoàn quân tinh nhuệ của ông được tối ưu sức mạnh, Salem phải chỉnh đốn lại hàng ngũ sao cho chỉ số của các người lính trong hàng tăng dần.

Salem thường dùng một thuật toán cố định để sắp xếp và chỉnh đốn hàng ngũ. Tuy nhiên thuật toán này lại tốn quá nhiều thời gian nên buộc Salem phải tìm cách sắp xếp khác. May mắn cho ông, tất cả các lính tinh nhuệ của ông đều đã được rèn luyện bài bản, chỉ cần gọi tên thì ngay lập tức 1 chuỗi hành động sau sẽ được những người lính ấy thực hiện:

• Nếu người lính được gọi có chỉ số lớn hơn người lính đứng kề bên phải thì 2 người lính này sẽ đổi chỗ cho nhau và quá trình này sẽ lặp đi lặp lại đến khi không còn người lính bên phải có chỉ số nhỏ hơn.
• Ngược lại, nếu người lính được gọi có chỉ số nhỏ hơn người lính đứng kề bên trái thì 2 người lính này sẽ đổi chỗ cho nhau và quá trình này sẽ lặp đi lặp lại đến khi không còn người lính bên trái có chỉ số lớn hơn.

Mỗi người lính khi được gọi tên sẽ thực hiện chuỗi hành động trên chỉ tốn 1 giây. Salem nhận thấy rằng không nhất thiết phải gọi tên toàn bộ n người lính mà chỉ cần gọi 1 số người trong đó thì toàn bộ hàng ngũ sẽ được sắp xếp. Salem không giỏi tính toán nên ông rất muốn biết xem số lượng người lính tối thiểu ông cần gọi tên là bao nhiêu. Ngoài ra, ông nhận thấy có thể có nhiều tập bé (có cùng số lượng phần tử tối thiểu) thỏa mãn. Là 1 người ham học hỏi, Salem tò mò muốn biết tập bé thứ K trong thứ tự từ điển là tập nào. Bạn hãy giúp Salem sắp xếp quân ngũ nhằm chuẩn bị tổng phản công.

Yêu cầu: Hãy cho biết số lượng người lính tối thiểu mà Salem cần gọi tên và tập bé thứ K trong thứ tự từ điển cần tìm.

Dữ liệu vào từ tệp văn bản BAI3.INP có cấu trúc:

• Dòng đầu chứa 2 số nguyên n ≤ 10⁵ và k ≤ 10¹⁸.
• Dòng thứ hai chứa n số nguyên là hoán vị của dãy số từ 1 đến n.

Dữ liệu đảm bảo luôn có nhiều hơn K tập thỏa mãn.

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI3.OUT có cấu trúc:

• Dòng đầu chứa số nguyên x là số lượng người lính cần gọi tên.
• x dòng sau, mỗi dòng chứa 1 số nguyên thuộc tập bé thứ K.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
5 1 3 5 1 4 2	3 1 2 4	Có nhiều tập bé 3 phần tử: (1, 2, 4), (1, 2, 5), … nhưng tập bé thứ 1 là: (1, 2, 4)

Chuỗi hành động là:

• Sau khi gọi tên người lính có chỉ số 1 (tức là ở vị trí 3 trong dãy ban đầu), dãy trở thành 1 3 5 4 2.
• Sau khi gọi tên người lính có chỉ số 2, dãy trở thành 1 2 3 5 4.
• Sau khi gọi tên người lính có chỉ số 4, dãy trở thành 1 2 3 4 5.

Như vậy, sau 3 lần gọi tên, quân ngũ đã được sắp xếp, và không có cách nào có số lần gọi bé hơn cũng như thứ tự từ điển bé hơn 1 2 4.

Chú ý:

• Có 30% số test có n ≤ 6 và k = 1.
• Có 30% số test tiếp theo có n ≤ 10⁵ và k = 1.
• Có 40% số test còn lại không có điều kiện gì thêm.

Bài 4 (5,0 điểm)

Thành Nam đang có lễ rước đức Thánh Trần nhân dịp kỷ niệm ngày giỗ của ngài. Để đảm bảo an toàn giao thông trên các tuyến phố mà đoàn rước đi qua, kể từ khi đoàn rước bắt đầu vào đầu tuyến phố cho đến khi đoàn rước đi qua hết tuyến phố, các phương tiện giao thông không được phép đi vào tuyến phố này. Tuy nhiên nếu có phương tiện nào đó đã ở trên tuyến phố trước khi đoàn rước đi vào tuyến phố thì nó vẫn di chuyển bình thường. Cũng trong khoảng thời gian đoàn rước đi trên các tuyến phố, An muốn thăm một người bạn ở trong thành phố.

Thành Nam có thể được mô tả như là hệ thống giao thông gồm các tuyến phố với các điểm giao cắt là đầu mút của mỗi tuyến phố, giữa hai nút giao cắt có không quá một tuyến phố. Với mỗi tuyến phố, thời gian đi của An và đoàn rước là như nhau.

Ví dụ: Nếu đoàn rước vào một tuyến phố nào đó ở thời điểm 10 và cần 5 đơn vị thời gian để đi hết tuyến phố thì An chỉ có thể vào tuyến phố trước thời điểm 10 hoặc từ thời điểm 15 hay muộn hơn.

Yêu cầu: Hãy xác định khoảng thời gian ít nhất An có thể đi đến đích.

Dữ liệu vào từ tệp văn bản BAI4.INP có cấu trúc:

• Dòng đầu tiên ghi hai số nguyên dương n, m (2 ≤ n ≤ 1000, 2 ≤ m ≤ 10000) là số điểm giao cắt và số tuyến phố. Các điểm giao cắt được đánh số từ 1 đến n.
• Dòng thứ hai chứa 4 số nguyên a, b, h, f với a, b là vị trí xuất phát và đích đến của An (Dữ liệu đảm bảo có đường đi từ a đến b); h là chênh lệch thời gian giữa thời điểm xuất phát của đoàn rước và thời điểm xuất phát của An (An xuất phát sau h đơn vị thời gian kể từ khi đoàn rước bắt đầu); f là số lượng điểm giao cắt có trên hành trình của đoàn rước.
• Dòng thứ ba chứa f số nguyên lần lượt là số hiệu các điểm giao cắt trên hành trình mà đoàn rước đi qua theo thứ tự. Dữ liệu đảm bảo rằng không có một tuyến phố nào mà đoàn rước đi qua nhiều hơn một lần.
• m dòng cuối cùng, mỗi dòng ghi ba số nguyên u, v và t thể hiện có một tuyến phố nối u và v với thời gian đi hết tuyến phố này là t (1 ≤ t ≤ 1000).

Các số trên cùng một dòng được ghi cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản BAI4.OUT có cấu trúc:

Một số nguyên là thời gian ngắn nhất mà An có thể đi từ a đến b.

Ví dụ:

BAI4.INP	BAI4.OUT
6 5 1 6 20 4 5 3 2 4 1 2 2 2 3 8 2 4 3 3 6 10 3 5 15	21

Chú ý: Có 40% số test với 2 ≤ n ≤ 100, 2 ≤ m ≤ 100.

---

Ghi chú:

• Sử dụng chương trình chấm thi tự động, học sinh đặt đúng tên tệp quy định, mỗi chương trình chạy không quá 1 giây.
• Cán bộ coi thi không giải thích gì thêm.