Đề Thi Học Sinh Giỏi Tin 11 Sở GD Quảng Nam 2022-2023 Có Đáp Án

TỔNG QUAN ĐỀ THI

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

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

Bài 1. (5.0 điểm) Đếm trại sinh

Trong đợt sinh hoạt trại 26/3 tại trường THPT A, Ban quản trại tổ chức cho các trại sinh tham gia trò chơi nối vòng tay lớn. Có N trại sinh tham gia, đứng thành vòng tròn, mỗi trại sinh lần lượt mang số hiệu từ 1 đến N. Người quản trại tiến hành đếm từ trại sinh thứ 1, qua trại sinh thứ 2, …đếm đến trại sinh thứ K, thì người này rời khỏi vòng tròn và trại sinh kế tiếp lại bắt đầu từ 1. Trò chơi kết thúc khi trên vòng tròn còn đúng 1 trại sinh, đây là trại sinh thắng cuộc.

Bạn An là trại sinh tham gia sinh hoạt trại, nên muốn mình sẽ là người chiến thắng (trại sinh còn lại sau cùng).

Yêu cầu: Hãy viết chương trình giúp bạn An chọn vị trí đứng trong vòng tròn để là người thắng cuộc trong trò chơi nối vòng tay lớn.

Dữ liệu vào: Đọc từ file văn bản COUNT.INP gồm:

• Dòng đầu tiên ghi số nguyên dương N là số trại sinh tham gia (N ≤ 10⁷);
• Dòng thứ hai ghi số nguyên dương K (K ≤ 2 x 10⁹).

Kết quả: Ghi ra file văn bản COUNT.OUT một số nguyên, là vị trí đứng trong vòng tròn của người thắng cuộc.

Ví dụ:

Ràng buộc:

• Có 40% test tương ứng 40% số điểm của bài với N ≤ 10³, K ≤ 10⁶;
• Có 30% test tương ứng 30% số điểm của bài với 10³ ≤ N ≤ 10⁶, K ≤ 10⁶;
• Có 30% test tương ứng 30% số điểm của bài với 10³ ≤ N ≤ 10⁷, K ≤ 2 x 10⁹.

Bài 2. (5.0 điểm) Ngôi sao may mắn

Để tham gia trò chơi tìm ngôi sao may mắn, An luôn suy nghĩ cách chọn một ngôi sao nào đó từ hai dãy đặt ngôi sao theo kiểu quanh co (thoạt đầu các ngôi sao của hai dãy chưa được chọn). Mỗi lượt chơi là quá trình An phải chọn ít nhất một ngôi sao theo cách sau:

- Chọn một ngôi sao tùy ý chưa từng được chọn từ một trong hai dãy đặt ngôi sao.

- Giả sử ở bước thứ T, An đã chọn ngôi sao có chỉ số i từ một dãy nào đó và nếu vẫn tiếp tục lượt chơi thì ở bước T + 1, An phải chọn một ngôi sao nào đó (chưa từng được chọn) từ dãy kia với chỉ số j mà i < j.

- Lượt chơi được coi là kết thúc nếu An không thể chọn tiếp được ngôi sao nào nữa (theo cách trên) hoặc An chủ động dừng cuộc chơi nếu muốn.

Điểm số mà An dành được sau mỗi lượt chơi chính là tổng của tất cả mã số đính kèm trên ngôi sao được chọn trong lượt chơi đó.

Yêu cầu: Xác định điểm số tối đa mà An đạt được từ lượt chơi đầu tiên.

Dữ liệu vào: Đọc từ file văn bản STAR.INP gồm:

• Dòng đầu tiên chứa số nguyên dương N (N ≤ 10⁶);
• Dòng thứ hai chứa N số nguyên, là mã số của các ngôi sao thuộc dãy thứ nhất;
• Dòng thứ ba chứa N số nguyên, là mã số của các ngôi sao thuộc dãy thứ hai.

(Tất cả các số hạng của hai dãy đều có giá trị tuyệt đối nhỏ hơn 10⁹, các số cách nhau một khoảng trắng)

Kết quả: Ghi ra file văn bản STAR.OUT một số nguyên, là điểm số cao nhất mà An đạt được từ lượt chơi đầu tiên.

Ví dụ:

Ràng buộc:

• Có 60% test tương ứng 60% số điểm của bài này với 1≤ N ≤ 20;
• Có 20% test tương ứng 20% số điểm của bài này với N ≤ 10³;
• Có 20% test tương ứng 20% số điểm của bài này với N ≤ 10⁶.

Bài 3. (5.0 điểm) Khỉ ăn chuối

Mạnh là ông chủ của một rạp xiếc khá nổi tiếng. Nhận thấy xiếc khỉ đang thu hút được nhiều người đến xem, ông đã quyết định đầu tư mua một số lượng lớn khỉ về để kiếm lời. Những con khỉ trong rạp xiếc rất thích ăn chuối, để dạy chúng làm xiếc, Mạnh đã chuẩn bị rất nhiều chuối cho chúng ăn. Chuối được chứa trong N thùng, mỗi thùng chứa một số lượng các quả chuối. Các thùng được đánh số từ 1 đến N.

Quy luật phát chuối cho một con khỉ là luôn phát hết chuối trong một thùng hoặc tất cả chuối chứa trong các thùng liên tiếp nhau.

Việc chia các thùng chuối cho bọn khỉ được thực hiện theo thứ tự từ thùng 1 đến thùng N, vì các con khỉ rất tham ăn nên các con khỉ đến sau luôn muốn nhận được lượng chuối lớn hơn hoặc bằng lượng chuối con khỉ đến trước nhận được. Để không lãng phí, Mạnh muốn tất cả các thùng chuối đều được phát hết.

Yêu cầu: Hãy giúp Mạnh tính xem số lượng con khỉ lớn nhất có thể nhận được chuối.

Dữ liệu vào: Đọc từ file văn bản BANANA.INP gồm:

- Dòng đầu tiên ghi số nguyên dương T là số bộ dữ liệu (T ≤ 100) trong đó mỗi bộ dữ liệu gồm:

+ Dòng đầu ghi số nguyên dương N là số lượng thùng chuối (2 ≤ N ≤ 5000);

+ Dòng tiếp theo chứa N số nguyên dương a­_i là số lượng chuối mỗi thùng, mỗi số cách nhau một dấu cách (1 ≤ a­_i ≤ 10⁹).

Kết quả: Ghi ra file văn bản BANANA.OUT gồm T dòng, mỗi dòng tương ứng với kết quả tính được của mỗi bộ dữ liệu vào.

Ví dụ:

Ràng buộc:

• Có 50% test tương ứng 50% số điểm của bài với T =1, 2 ≤ N ≤ 100, 1 ≤ a­_i ≤ 10⁵;
• Có 30% test tương ứng 30% số điểm của bài với T =1, 100 ≤ N ≤ 1000, 1 ≤ a­_i ≤ 10⁹;
• Có 20% test tương ứng 20% số điểm của bài với T ≤ 100, 1000 ≤ N ≤ 5000, 1 ≤ a­_i ≤ 10⁹.

Bài 4. (5.0 điểm) Tình đồng chí

Chị Liên là một giao liên hoạt động cách mạng trong kháng chiến chống Pháp. Chị nổi tiếng là người gan dạ và khôn khéo. Thực dân Pháp muốn có được chị để thực hiện mọi âm mưu tiêu diệt cán bộ cách mạng của ta. Trong một lần đi công tác, chị không may bị giặc Pháp bắt giam.

Được biết, nơi chị bị giam là một nhà giam đặc biệt hình chữ nhật, có P x Q phòng giam. Nhà giam được đánh số phòng theo chiều từ trên xuống dưới bắt đầu 1 đến P, đánh số phòng từ 1 đến Q theo chiều từ trái qua phải. Giữa hai phòng giam sát nhau có cửa thông nhau, muốn mở cửa để đi từ phòng này sang phòng kia phải mất một khoảng thời gian nhất định nào đó.

Sáu là một chiến sĩ đặc công được giao nhiệm vụ giải cứu chị Liên. Sau hơn hai giờ đồng hồ dò tìm trong nhà giam, anh mới phát hiện giặc Pháp giam chị tại phòng giam cuối cùng [P,Q] - dòng P cột Q.

Còn về phía Pháp, chúng cho rằng đặc công của ta đang cấp bách tìm kiếm chị nên tìm cách tra tấn dã man nhằm moi hết thông tin từ chị rồi nhanh chóng thủ tiêu. Chúng nghĩ rằng, đặc công của ta sẽ kịp thời tìm ra được chị. Thời gian thủ tiêu chị Liên sắp đến…

Yêu cầu: Bạn nghĩ xem, anh Sáu mất thời gian ít nhất là bao lâu để cứu và đưa chị Liên ra khỏi nhà giam của Pháp?

Dữ liệu vào: Đọc từ file văn bản COMRADE.INP gồm:

Dòng đầu tiên ghi số nguyên dương T là số bộ dữ liệu (T ≤ 10) trong đó mỗi bộ dữ liệu gồm:

• Dòng thứ nhất là hai số nguyên P và Q cách nhau một khoảng trắng (1 ≤ P, Q ≤ 1000);
• Trong P dòng tiếp theo, mỗi dòng gồm Q-1 số nguyên a_ij là khoảng thời gian để mở cửa từ phòng giam [i, j] sang phòng giam [i, j+1], hoặc khoảng thời gian để mở cửa từ phòng giam [i, j+1] sang phòng giam [i, j] (1 ≤ a_ij ≤ 10⁵);
• Trong P-1 dòng tiếp theo, mỗi dòng gồm Q số nguyên b_ij là khoảng thời gian để mở cửa từ phòng giam [i, j] sang phòng giam [i +1, j] hoặc khoảng thời gian để mở cửa từ phòng giam [i+1, j] sang phòng giam [i, j] (1 ≤ b_ij ≤ 10⁵).

Kết quả: Ghi ra file văn bản COMRADE.OUT gồm T dòng, mỗi dòng tương ứng với kết quả tính được của mỗi bộ dữ liệu vào.

Ví dụ:

Ràng buộc :

• Có 50% test tương ứng với 50% số điểm bài với T = 1 và 1 ≤ P, Q ≤ 20;
• Có 30% test tương ứng với 30% số điểm bài với T = 1 và P, Q ≤ 1000;
• Có 20% test tương ứng với 20% số điểm bài với T ≤ 10 và P, Q ≤ 1000.

--------------- Hết ---------------

Thí sinh không được sử dụng tài liệu; Cán bộ coi thi không giải thích gì thêm.
Họ và tên thí sinh: .............................................................. Số báo danh: ...............................

HƯỚNG DẪN CHẤM MÔN TIN HỌC

Bài thi chấm bằng test, và chấm bằng phần mềm Themis kèm theo

(mới nhất của thầy Lê Minh Hoàng và Đỗ Đức Đông)

Bài 1 (5.0 điểm) gồm có 50 test, mỗi test 0,1 điểm, bộ nhớ 1024 MB

• Có 40% test tương ứng 40% số điểm của bài với N ≤ 10³, K ≤ 10⁶ thời gian thực hiện 1s.
• Có 30% test tương ứng 30% số điểm của bài với 10³ ≤ N ≤ 10⁶, K ≤ 10⁶ thời gian thực hiện 1s.
• Có 20% test tương ứng 20% số điểm của bài với 10³ ≤ N ≤ 10⁷, K ≤ 2 x 10⁹ thời gian thực hiện 1s.
• Có 10% test tương ứng 10% số điểm của bài với 10⁶ ≤ N ≤ 10⁷, K ≤ 2 x 10⁹ thời gian thực hiện 3s.

Bài 2 (5.0 điểm) gồm có 40 test, mỗi test 0,125 điểm, thời gian 1s, bộ nhớ 1024 MB

• Có 60% test tương ứng 60% số điểm của bài này với 1≤ N ≤ 20;
• Có 20% test tương ứng 20% số điểm của bài này với N ≤ 10³;
• Có 20% test tương ứng 20% số điểm của bài này với N ≤ 10⁶.

Bài 3 (5.0 điểm) gồm có 40 test, mỗi test 0,125 điểm, bộ nhớ 1024 MB

• Có 50% test tương ứng 50% số điểm của bài với T = 1, 2 ≤ N ≤ 100, 1 ≤ a­_i ≤ 10⁵ thời gian thực hiện 1s.
• Có 30% test tương ứng 30% số điểm của bài với T = 1, 100 ≤ N ≤ 1000, 1 ≤ a­_i ≤ 10⁹ thời gian thực hiện 1s.
• Có 20% test tương ứng 20% số điểm của bài với T ≤ 100, 1000 ≤ N ≤ 5000, 1 ≤ a­_i ≤ 10⁹ thời gian thực hiện 2s.

Bài 4 (5.0 điểm) gồm có 40 test, mỗi test 0,125 điểm, bộ nhớ 1024 MB

• Có 50% test tương ứng với 50% số điểm bài với T = 1 và 1 ≤ P, Q ≤ 20 thời gian thực hiện 1s.
• Có 30% test tương ứng với 30% số điểm bài với T = 1 và P, Q ≤ 1000 thời gian thực hiện 1s.
• Có 10% test tương ứng với 10% số điểm bài với T ≤ 10 và P, Q ≤ 1000 thời gian thực hiện 1s.
• Có 10% test tương ứng với 10% số điểm bài với T ≤ 10 và P, Q ≤ 1000 thời gian thực hiện 2s.

---------------HẾT ---------------