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

Trang 1/4

SỞ GIÁO DỤC VÀ ĐÀO TẠO

TỈNH QUẢNG NAM

KỲ THI HỌC SINH GIỎI CẤP TỈNH THPT

NĂM HỌC 2021 - 2022

(Đề gồm có 04 trang)

Môn thi: TIN HỌC 11 (CHUYÊN) Thời gian: 180 phút (không kể thời gian giao đề) Ngày thi: 22/3/2022

Tổng quan về đề thi

Tên bài Tên file chương trình Dữ liệu vào Dữ liệu ra Thời

gian

Bài 1: Tặng quà QUATANG.* QUATANG.INP QUATANG.OUT 1s

Bài 2: Dự tiệc GHENGOI.* GHENGOI.INP GHENGOI.OUT 1s

Bài 3: Phân tích số PHANTICH.* PHANTICH.INP PHANTICH.OUT 1s

Bài 4: Cắm trại CAMTRAI.* CAMTRAI.INP CAMTRAI.OUT 1s

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) Tặng quà

An đạt giải cao trong kỳ thi Khoa học kĩ thuật cấp tỉnh vừa qua nên mẹ đã thưởng cho An một

chuyến đi du lịch đến thành phố Nha Trang. Tại đây, An đã tham quan nhiều nơi và mua nhiều

quà cho 3 người trong gia đình gồm ba, mẹ và em của An. Có N món quà được đánh số từ 1 đến

N, trong đó món quà thứ i có giá trị sử dụng là ai . Gọi T1, T2, T3 lần lượt là tổng giá trị các món

quà của mỗi người; Tmax và Tmin lần lượt là giá trị lớn nhất và nhỏ nhất của T1, T2, T3.

Yêu cầu: An muốn thể hiện sự công bằng của mình đối với ba, mẹ và em nên An nghĩ cách

chia N món quà trên cho 3 người sao cho chênh lệch của Tmax và Tmin là nhỏ nhất. Các bạn

chuyên Tin 11 hãy giúp An chia quà nhé!

Dữ liệu vào: Từ tệp văn bản QUATANG.INP gồm:

- Dòng thứ nhất là số nguyên N (1 ≤ N ≤ 15);

- Dòng thứ hai gồm N số nguyên a1, a2, …, aN là giá trị của các món quà (1 ≤ ai ≤ 103).

Dữ liệu ra: Ghi ra tệp văn bản QUATANG.OUT gồm một số nguyên duy nhất cần tìm.

Ví dụ:

QUATANG.INP QUATANG.OUT 6 5 7 8 4 3 15

2

ĐỀ CHÍNH THỨC

Trang 2/4

Ràng buộc:

 Sub1: Có 50% test tương ứng 50% số điểm của bài với N ≤ 5 và ai ≤ 102;

 Sub2: Có 30% test tương ứng 30% số điểm của bài với N ≤ 10 và ai ≤ 102;

 Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với N ≤ 15 và ai ≤ 103.

Bài 2: (5.0 điểm) Dự tiệc

Công ty Bảo hiểm AB tổ chức buổi tiệc nhằm tri ân những khách hàng đã tham gia mua

bảo hiểm. Giám đốc Công ty muốn tất cả các khách hàng đến dự tiệc được thoải mái và vui vẻ

nên đã yêu cầu nhân viên lễ tân chuẩn bị trước những bàn tiệc với số lượng người trong mỗi

bàn có thể khác nhau để tiện bố trí cho mỗi nhóm khách hàng muốn ngồi chung một bàn. Nhân

viên lễ tân đã bố trí M bàn tiệc, bàn thứ i có đủ ghế ngồi cho ai người. Trước khi bắt đầu vào

buổi tiệc, có N nhóm khách hàng đến dự, nhóm thứ j có bj người. Để khách hàng đến dự tiệc

được ngồi cùng nhóm trong một bàn, nhân viên lễ tân linh động bằng cách kê thêm ghế cho

những bàn thiếu ghế và nếu có những bàn nào thừa ghế thì sẽ lấy bớt đi cho vừa đủ.

Yêu cầu: Bạn hãy giúp nhân viên lễ tân tìm phương án bố trí khách ngồi sao cho tổng số các

ghế kê thêm và các ghế lấy bớt là ít nhất.

Dữ liệu vào: Từ tệp văn bản GHENGOI.INP gồm 03 dòng:

- Dòng thứ nhất gồm hai số nguyên dương M, N (0 < N ≤ M ≤ 104);

- Dòng thứ hai ghi M số nguyên ai (0 < ai < 109, i = 1, …, M);

- Dòng cuối cùng ghi N số bj (0 < bj < 109, j = 1, ..., N).

Dữ liệu ra: Ghi ra tệp văn bản GHENGOI.OUT gồm duy nhất một số nguyên là số lượng ít

nhất các ghế đã chuyển ra, chuyển vào của tất cả các bàn.

Ví dụ:

GHENGOI.INP GHENGOI.OUT

5 4

5 6 9 10 7

6 8 3 8

4

Ràng buộc:

 Sub1: Có 40% test tương ứng 40% số điểm của bài với 0 <N ≤ M ≤ 10 và ai, bj ≤ 10;

 Sub2: Có 40% test tương ứng 40% số điểm của bài với 0 <N ≤ M ≤ 102 và ai, bj ≤ 104;

 Sub3: Có 20% test tương ứng 20% số điểm của bài với 0 <N ≤ M ≤ 104 và ai, bj < 109.