Đề thi chọn học sinh giỏi THPT cấp tỉnh môn Tin học - Năm học 2019-2020 - Sở GD&ĐT Ninh Bình (Đề 1) (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH
NĂM HỌC 2019 - 2020
MÔN: TIN
Ngày thi: 11/9/2019
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 03 trang
TỔNG QUAN BÀI THI NGÀY THỨ NHẤT 
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Câu 1
Nhà hàng
EGG.*
EGG.INP
EGG.OUT
Câu 2
Xếp hộp lồng nhau
BOX.*
BOX.INP
BOX.OUT
Câu 3
Bài toán Robot
ROBOT.*
ROBOT.INP
ROBOT.OUT
Phần mở rộng của File chương trình là PAS hoặc CPP tùy theo ngôn ngữ lập trình sử dụng là Pascal hoặc C++
Câu 1. Nhà hàng (6.0 điểm)
Nhà hàng Pizza_Egg có một số nông dân chuyên cung cấp trứng sạch và mỗi người có một giá bán khác nhau. Mỗi người nông dân chỉ có một số lượng trứng nhất định mỗi ngày, nhà hàng có thể mua một số trứng từ mỗi người nông dân, ít hơn hoặc bằng số lượng trứng của mỗi người nông dân đó. Biết số lượng trứng mỗi ngày mà nhà hàng cần, giá mỗi quả trứng và số lượng trứng mà mỗi người nông dân có. 
Yêu cầu: Hãy tính số tiền ít nhất mà nhà hàng cần để mua được số trứng đó. Giả thiết tổng số trứng của người nông dân đủ đáp ứng nhu cầu của nhà hàng.
Dữ liệu: Vào từ file EGG.INP
- Dòng đầu tiên chứa hai số nguyên N, M. N là số trứng mà nhà hàng cần mỗi ngày (), M là số người nông dân cung cấp trứng cho nhà hàng ().
- Dòng thứ i trong M dòng tiếp theo, chứa hai số nguyên Ai và Bi cách nhau một khoảng trắng. Ai () là giá một quả trứng của người nông dân i; Bi () là số trứng tối đa mà một người nông dân có thể bán cho nhà hàng.
Kết quả: ghi ra file EGG.OUT một số nguyên là số tiền nhỏ nhất mà nhà hàng cần để mua đủ trứng mỗi ngày.
Ví dụ:
EGG.INP
EGG.OUT
50 5
5 30
10 40
3 10
8 80
7 30
250
Ràng buộc:
Có 70% số test ứng với 70% số điểm của bài có 
Có 30% số test ứng với 30% số điểm của bài có 
Câu 2. Xếp hộp lồng nhau (7.0 điểm)
Nguyên vật liệu nhập về kho của một xí nghiệp được đóng trong các thùng giấy hình hộp chữ nhật. Để giải phóng chỗ người thủ kho phải xếp những hộp giấy rỗng lồng vào nhau cho gọn. Giả sử có N hộp giấy rỗng, các hộp được đánh số từ 1 đến N. Với mỗi hộp giấy rỗng, người thủ kho biết được chính xác độ dài hai cạnh đáy của hộp là a và b.
Yêu cầu: Hãy giúp người thủ kho xếp các hộp giấy rỗng sao cho trong số các dãy hộp giấy xếp chồng nhau ta được một dãy các hộp xếp chồng nhau có số hộp giấy lớn nhất có thể.
Dữ liệu vào: Cho trong file văn bản BOX.INP, có cấu trúc như sau:
Dòng 1: Ghi số nguyên dương N, là số lượng hộp giấy rỗng. (1 ≤ N ≤ 1000)
N dòng tiếp theo: Mỗi dòng ghi hai số nguyên dương ai bi cách nhau một khoảng trắng, là độ dài hai cạnh đáy của hộp giấy rỗng thứ i. (1 ≤ ai, bi ≤ 10000)
Dữ liệu ra: Ghi ra file văn bản BOX.OUT số nguyên dương M là kết quả của bài toán.
Ví dụ:
BOX.INP
BOX.OUT
5
1 5
5 7
6 4
3 6
2 5
3
Giải thích: số lượng hộp giấy xếp lồng nhau lớn nhất là 3, một số cách xếp theo chỉ số các hộp từ ngoài vào trong: 2 3 5; hoặc 2 3 1; hoặc 2 4 5; ...
Ràng buộc:
Có 40% số test ứng với 40% số điểm của bài có 
Có 60% số test ứng với 60% số điểm của bài có 
Câu 3. Bài toán Robot (7 điểm)
Trên một lưới ô vuông M*N (M, N < 1000), người ta đặt robot A ở góc trái trên, robot B ở góc phải dưới. Mỗi ô của lưới có thể đặt một vật cản hoặc không (ô trái trên và phải dưới không có vật cản). Hai robot bắt đầu di chuyển đồng thời với tốc độ như nhau và không robot nào được dừng lại trong khi robot kia di chuyển (trừ khi nó không thể đi được nữa). Tại mỗi bước, robot chỉ có thể di chuyển theo 4 hướng - đi lên, đi xuống, sang trái, sang phải - vào các ô kề cạnh. Hai robot sẽ gặp nhau nếu chúng đứng trong cùng một ô vuông. 
Yêu cầu: Bạn hãy lập trình tìm cách di chuyển ít bước nhất mà 2 robot phải thực hiện để hai Robot có thể gặp nhau. 
Dữ liệu: Lấy từ trong file ROBOT.INP .
- Dòng đầu ghi 2 số M, N.
- M dòng tiếp theo, mỗi dòng ghi N số 0 hoặc 1 mô tả trạng thái của các ô vuông: 1 - có vật cản, 0 - không có vật cản.
Các số trên cùng một dòng của file dữ liệu cách nhau ít nhất một khoảng trắng.
Kết quả: Ghi ra file ROBOT.OUT:
- Nếu 2 robot không thể gặp nhau thì ghi ký tự #.
- Ngược lại, ghi số bước ít nhất để hai robot gặp nhau.
Ví dụ: 
ROBOT.INP
ROBOT.OUT
4 6 
0 1 1 0 0 0 
0 0 0 0 0 1 
0 0 1 0 0 1
0 1 0 1 0 0
4 
-----Hết----
Họ và tên thí sinh :....................................................... Số báo danh .............................
Họ và tên, chữ ký:	Giám thị 1:.....................................................................................
 	Giám thị 2:.....................................................................................