HSG THPT Quảng Ninh 2024-2025 (Bảng B)

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH QUẢNG NINH ĐỀ THI CHÍNH THỨC
(Đề thi này có 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THPT NĂM 2024 Môn thi: Tin học - Bảng B
Ngày thi: 05/12/2024
Thời gian làm bài: 180 phút, không kể thời gian phát đề

---

Tổng quan đề thi

Bài	Tên bài	Tệp chương trình	Tệp dữ liệu vào	Tệp kết quả	Bộ nhớ	Thời gian/test	Điểm
1	Doanh thu	TURNO.*	TURNO.INP	TURNO.OUT	1024 MB	1 giây	6
2	Dãy số	SEQ.*	SEQ.INP	SEQ.OUT	1024 MB	1 giây	6
3	Khảo cổ	ARCHA.*	ARCHA.INP	ARCHA.OUT	1024 MB	1 giây	5
4	Mê cung	MAZE.*	MAZE.INP	MAZE.OUT	1024 MB	1 giây	3

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

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

Bài 1. Doanh thu (6 điểm)

Một nhà hàng Buffe mỗi ngày có n khách hàng, tuổi của khách hàng thứ i là a_i (1 ≤ i ≤ n). Nhà hàng niêm yết giá là 300.000 đồng/1 người và có kèm chương trình khuyến mại theo độ tuổi của khách hàng như sau:

Giả sử một khách hàng thứ i với tuổi là a_i. Khi đó:

1. Nếu a_i ≤ 5 thì khách hàng đó được miễn phí.
2. Nếu 5 < a_i ≤ 10 thì khách hàng đó được giảm giá 80%.
3. Nếu 10 < a_i ≤ 15 thì khách hàng đó được giảm giá 50%.
4. Nếu a_i ≥ 60 thì khách hàng đó được giảm giá 20%.

Yêu cầu: Quản lý muốn tính tổng doanh thu của nhà hàng trong một ngày, để có số liệu kịp thời đánh giá và điều chỉnh giúp nhà hàng phát triển tốt hơn.

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

• Dòng thứ nhất chứa số nguyên n (1 ≤ n ≤ 10⁷) là số lượng khách trong một ngày;
• Dòng thứ hai gồm n nguyên dương a₁, a₂, …, a_n, số nguyên a_i (1 ≤ a_i ≤ 100) là tuổi của khách hàng thứ i (1 ≤ i ≤ n).

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

Kết quả: Ghi ra file văn bản TURNO.OUT, một số nguyên là tổng thu nhập của nhà hàng dựa theo yêu cầu của bài toán. Đơn vị mặc định là đồng.

Ví dụ:

TURNO.INP	TURNO.OUT
6 26 2 9 67 39 15	1050000

Ràng buộc:

• Có 60% số test ứng với 60% số điểm của bài có n ≤ 10³;
• Có 40% số test còn lại ứng với 40% số điểm của bài có n ≤ 10⁷.

Bài 2. Dãy số (6 điểm)

Để chuẩn bị cho kỳ thi học sinh giỏi cấp tỉnh năm nay thầy Minh giáo viên dạy Tin học của trường muốn kiểm tra kiến thức lập trình của đội tuyển học sinh giỏi cấp tỉnh môn Tin học. Thầy ra một bài toán như sau:

Cho một dãy A gồm n số nguyên không âm a₁, a₂, …, a_n. Sau đó biến đổi dãy A thành dãy A’ sao cho phần tử thứ i dãy A’ có giá trị bằng tổng các giá trị từ phần tử thứ nhất đến phần tử thứ i của dãy A, với i = 1, 2, …, n.

Xét ví dụ, với dãy A có 5 phần tử là 0, 1, 0, 2, 2. Sau khi biến đổi được dãy A’ là 0, 1, 1, 3, 5.

Tiếp theo, thầy cho một dãy số B gồm m số nguyên không âm b₁, b₂, …, b_m và thầy đưa ra yêu cầu tìm vị trí xuất hiện các phần tử của dãy B trong dãy A’.

Yêu cầu: Hãy tìm vị trí xuất hiện của phần tử b_j (1 ≤ j ≤ m) trong dãy A’.

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

• Dòng thứ nhất chứa hai số nguyên dương n, m (1 ≤ n, m ≤ 10⁶) lần lượt là số lượng phần tử của dãy A và dãy B;
• Dòng thứ hai gồm n số nguyên không âm a₁, a₂, …, a_n (0 ≤ a_i ≤ 10⁶, 1 ≤ i ≤ n);
• Dòng thứ ba gồm m số nguyên không âm b₁, b₂, …, b_m (0 ≤ b_j ≤ 10⁶, 1 ≤ j ≤ m).

Kết quả: Ghi ra file văn bản SEQ.OUT, một dòng gồm m số nguyên, số thứ j là vị trí xuất hiện của phần tử b_j (1 ≤ j ≤ m) trong dãy A’, nếu có nhiều vị trí hãy in ra vị trí xuất hiện đầu tiên, nếu b_j không xuất hiện trong dãy A’ thì số thứ j in ra −1.

Các số trên một dòng của file dữ liệu vào/ra được ghi cách nhau bởi dấu cách.

Ví dụ:

SEQ.INP	SEQ.OUT
5 4 0 1 0 2 2 1 3 6 5	2 4 -1 5

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài có n, m ≤ 10³;
• Có 30% số test ứng với 30% số điểm của bài có n, m ≤ 3.10⁴;
• Có 30% số test còn lại ứng với 30% số điểm của bài có n, m ≤ 10⁶.

Bài 3. Khảo cổ (5 điểm)

Một nhóm khảo cổ họ tìm thấy những cổ vật mà trên đó có thông tin được mã hoá như sau:

• Dòng đầu tiên là số 0 hoặc số 1;
• Dòng thứ hai là một dãy các kí tự chữ cái la tinh in thường (gọi là đoạn mã V).

Qua nghiên cứu một cổ vật, họ phát hiện ra rằng các thông tin được mã hoá theo mô tả trên sau khi giải mã sẽ thu được một đoạn mã thông tin gốc S. Quy luật biến đổi ngược lại từ đoạn mã gốc S về đoạn mã V theo các bước như sau:

• Bước 1: Đoạn mã gốc S được nhân đôi thành đoạn mã T;
• Bước 2: Chọn một trong các kí tự của đoạn mã T, nhân đôi kí tự đó làm cho độ dài đoạn mã T tăng thêm một kí tự, ta được một đoạn mã U;
• Bước 3: Nếu dòng đầu tiên trên cổ vật là số 1 thì đảo ngược đoạn mã U sẽ được đoạn mã V, nếu dòng đầu tiên trên cổ vật là số 0 thì đoạn mã U chính là đoạn mã V.

Yêu cầu: Dựa vào thông tin mỗi cổ vật, bạn hãy lập trình giúp các nhà khảo cổ tìm kí tự được nhân đôi ở bước 2 và đoạn mã thông tin gốc của cổ vật đó.

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

• Dòng thứ nhất chứa số nguyên K (0 ≤ K ≤ 1);
• Dòng thứ hai chứa đoạn mã V có độ dài không vượt quá 10⁶ kí tự.

Kết quả: Ghi ra file văn bản ARCHA.OUT:

• Dòng thứ nhất ghi ra kí tự đã được nhân đôi;
• Dòng thứ hai ghi ra đoạn mã gốc S.

Ví dụ:

ARCHA.INP	ARCHA.OUT
1 ebbaeba	b abe
0 ttpcdtpcd	t tpcd

Ràng buộc:

• Có 40% số test ứng với 40% số điểm của bài có độ dài của V không quá 10²;
• Có 30% số test ứng với 30% số điểm của bài có độ dài của V không quá 10⁵;
• Có 30% số test còn lại ứng với 30% số điểm của bài có độ dài của V không quá 10⁶.

Bài 4. Mê cung (3 điểm)

Hai bạn An và Bình cùng nhau chơi trò chơi mê cung trong một công viên. Mê cung có hình dạng là một bảng hình vuông kích thước n × n, các hàng của bả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 n từ trái sang phải. Ô nằm giao giữa hàng i, cột j là ô (i, j) chứa số nguyên a_ij nhận một trong hai giá trị 0 và 1. Nếu một người chơi đang ở hàng i và chọn cột j có giá trị a_ij = 1 thì có một cánh cửa thần kỳ được mở ra và đưa người đó đến hàng thứ j (nếu a_ij = 0 thì không có cánh cửa nào được mở ra). Mỗi hàng có ít nhất một cánh cửa, không có cánh cửa nào đưa người chơi đến chính hàng mà người đó đang đứng.

An xuất phát từ hàng số 1, Bình xuất phát từ hàng số n. Hai bạn đồng thời cùng chọn cho mình một cánh cửa để đi đến một hàng khác, nếu hai bạn không gặp nhau ở cùng một hàng thì mỗi bạn lại tiếp tục chọn cho mình một cánh cửa ở hàng hiện tại để tiếp tục đi đến một hàng tiếp theo. Quá trình đó cứ tiếp tục cho đến khi hai bạn gặp nhau ở cùng một hàng nào đó của mê cung.

Yêu cầu: Bạn hãy giúp An và Bình tìm số lần chọn ô có cánh cửa ít nhất để hai bạn gặp nhau tại cùng một hàng nào đó của mê cung.

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

• Dòng thứ nhất chứa một số nguyên dương n (2 ≤ n ≤ 5.10³);
• n dòng tiếp theo, dòng thứ i chứa n số nguyên a_i1, a_i2, …, a_in (có giá trị 0 hoặc 1).

Hai số liên tiếp trên một dòng được ghi liền nhau, không có dấu cách.

Kết quả: Ghi ra file văn bản MAZE.OUT, một số nguyên là số lần chọn ô có cánh cửa ít nhất để hai bạn gặp nhau tại cùng một hàng nào đó của mê cung. Biết rằng dữ liệu đầu vào luôn tồn tại ít nhất một phương án để hai bạn gặp nhau tại một hàng nào đó của mê cung.

Ví dụ:

MAZE.INP	MAZE.OUT	Giải thích
5 01000 00100 00010 00101 00010	2	Lần 1: An chọn ô (1,2) có cánh cửa đưa đến hàng số 2. Bình chọn ô (5,4) có cánh cửa đưa đến hàng số 4. Lần 2: An chọn ô (2,3) có cánh cửa đưa đến hàng số 3. Bình chọn ô (4,3) có cánh cửa đưa đến hàng số 3. Hai bạn gặp nhau tại hàng số 3.

Ràng buộc:

• Có 60% số test ứng với 60% số điểm của bài có n ≤ 10²;
• Có 30% số test ứng với 30% số điểm của bài có n ≤ 2.10³;
• Có 10% số test còn lại ứng với 10% số điểm của bài có n ≤ 5.10³.

---

• Thí sinh không được sử dụng tài liệu.
• Giám thị coi thi không giải thích gì thêm.