Đề thi chọn học sinh giỏi THPT cấp tỉnh năm 2017 môn Tin học - Sở GD&ĐT Ninh Bình (Đề 2) (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 2017
MÔN: TIN HỌC
Ngày thi: 26/4/2017
(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
Bài
Tên bài
Tên Chương trình
Input
Output
Thời gian/Test
1
Trò chơi lấy bi
GAME.*
GAME.INP
GAME.OUT
1 giây
2
Cầu phao
BRIDGE.*
BRIDGE.INP
BRIDGE.OUT
1 giây
3
Thăm bạn 
FESTIVAL.*
FESTIVAL.INP
FESTIVAL.OUT
1 giây
Trong đó: * là phần mở rộng PAS hoặc CPP tùy ngôn ngữ lập trình Pascal hoặc C++
Câu 1 (6.0 điểm): Trò chơi lấy bi
Trò chơi Lấy bi được mô tả như sau, có 4 loại bi với các màu A, B, C, D. Số lượng mỗi loại bi không quá 8 viên. Người chơi chỉ có thể chọn và lấy các viên bi với số lượng theo một trong 5 quy tắc sau:
Lấy 2 bi màu A, một bi màu B, 2 bi màu D;
Lấy cả 4 loại bi, mỗi loại một viên;
Lấy 2 bi màu C, 1 bi màu D;
Lấy 3 bi màu B;
Lấy 1 bi màu A và 1 bi màu D.
Hai bạn An và Bình chơi theo kiểu lấy bi luân phiên. An luôn là người lấy trước. Người nào không có cách lấy bi nữa là thua. Giả sử rằng cả hai người đều chơi giỏi như nhau (ai cũng tính được cơ hội thắng của mình). 
Ví dụ : Ban đầu có 1 bi màu A, 5 bi màu B, 3 bi màu D (ABBBBBDDD). Bình sẽ luôn thắng vì nếu An lấy 3 bi màu B thì còn lại (ABBDDD) và Bình lấy 1 bi màu A và 1 bi màu D, số bi còn lại là (BBDD) và An không còn cách lấy nữa. Ngược lại nếu An lấy 1 bi màu A và 1 bi màu D thì Bình lấy 3 bi màu B và kết quả An vẫn bị thua.
Yêu cầu: Với số lượng bi cho trước, hãy cho biết ai là người thắng trong lần chơi đó.
Dữ liệu: 
+ Dòng đầu ghi số nguyên dương N là số ván chơi (1 ≤ N ≤ 100).
+ N dòng tiếp mỗi dòng mô tả số bi mỗi loại lúc ban đầu của một ván chơi, gồm 4 số nguyên không âm và không vượt quá 8, lần lượt là số bi màu A, B, C, D (các số cách nhau bởi một dấu cách).
Kết quả: Ứng với mô tả N ván chơi trong tệp dữ liệu, chương trình của bạn phải in N dòng, mỗi dòng ghi “A” hoặc “B” (“A” nếu An thắng hoặc “B” nếu Bình thắng).
Ràng buộc: Có 50% test ứng với 50% điểm của bài có giá trị N ≤ 5.
Ví dụ:
GAME.INP
GAME.OUT
6
0 2 0 2
1 3 1 3
1 5 0 3
3 3 3 3
8 8 6 7
8 8 8 8
B
A
B
B
B
A
Câu 2 (7.0 điểm): Cầu phao	 
Mưa to liên tục mấy ngày liền đã biến con suối ven làng thành một con sông thực sự. Để học sinh có thể đi học an toàn người ta quyết định bắc tạm một cầu phao. Nguyên vật liệu làm cầu được một công trường gần đó cho mượn, bao gồm x khúc gỗ tròn độ dài a và y khúc gỗ tròn độ dài b. Tất cả chúng đều có cùng một bán kính.
Cầu phao phải được ghép từ m hàng gỗ. Mỗi hàng bao gồm một hoặc một vài khúc gỗ. Các khúc gỗ phải được giữ nguyên, không được cưa ngắn. 
Người ta muốn xây dựng cây cầu với độ rộng lớn nhất có thể. Độ rộng của cầu được xác định bởi độ dài của hàng nhỏ nhất. 
Ví dụ: Cầu cần xây dựng có 7 hàng và ta có 6 khúc gỗ độ dài 3; 10 khúc gỗ độ dài 2, khi đó độ rộng tối đa của cầu là 5.
Yêu cầu: Cho x, a, y, b và m, tất cả đều nguyên và có giá trị không vượt quá 150. Tổng số lượng các khúc gỗ không ít hơn m. Hãy xác định độ rộng tối đa của cây cầu.
Dữ liệu: Vào từ file văn bản BRIDGE.INP gồm 1 dòng chứa 5 số nguyên x, a, y, b và m.
Kết quả: Đưa ra file văn bản BRIDGE.OUT một số nguyên là độ rộng tối đa của cây cầu.
Ví dụ:
BRIDGE.INP
BRIDGE.OUT
6 3 10 2 7
5
Câu 3 (7.0 điểm): Thăm bạn trong ngày hội 
Trong dịp lễ kỉ niệm 25 năm tái lập Tỉnh Ninh Bình, Thành phố Ninh Bình có tổ chức một đoàn diễu hành trên đường phố. Để đảm bảo an toàn giao thông, trên các tuyến phố mà đoàn diễu hành đi qua, kể từ khi đoàn diễu hành bắt đầu đi vào đầu phố cho đến khi đoàn diễu hành đi qua hết phố, các phương tiện giao thông không được phép đi vào phố này kể cả từ hai đầu. Tuy nhiên nếu có phương tiện nào đó đã ở trên phố trước khi đoàn diễu hành đi vào phố thì nó vẫn di chuyển bình thường (kể cả từ hai đầu phố). Cũng trong khoảng thời gian đoàn diễu hành đi trên các phố, Hùng muốn thăm một người bạn ở trong thành phố.
Thành phố Ninh Bình 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ố. Với mỗi tuyến phố, thời gian mà Hùng đi hết nó bằng với thời gian mà đoàn diễu hành đi hết tuyến phố này.
Ví dụ: Nếu như đoàn diễu hành đi 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 thì Hùng không thể đi vào phố này ở các thời điểm 10, 11, 12, 13, 14. Cậu ta chỉ có thể vào phố ở thời điểm 9 hoặc sớm hơn, hoặc ở thời điểm 15 hoặc muộn hơn.
Yêu cầu: Hãy xác định thời gian nhanh nhất mà Hùng đi đến đích (giả sử rằng luôn có đường đi cho Hùng có thể đi đến đích).
Dữ liệu: Vào từ file văn bản FESTIVAL.INP
+ 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 vị trí xuất phát và đích đến của Hùng; H là chênh lệch thời gian giữa thời điểm xuất phát của đoàn diễu hành và thời điểm xuất phát của Hùng (Hùng xuất phát sau H đơn vị thời gian kể từ khi đoàn diễu hành bắt đầu); F là số lượng điểm giao cắt có trên hành trình của đoàn diễu hành.
+ 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 diễu hành đi qua theo thứ tự. Đảm bảo rằng không có một tuyến phố nào mà đoàn diễu hành đ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 P, Q và L thể hiện có một tuyến phố nối P và Q với thời gian đi hết nó là L (của Hùng cũng như của đoàn diễu hành). Giá trị của L nằm trong khoảng [1,1000].
Kết quả: Ghi ra file FESTIVAL.OUT
Một số nguyên duy nhất là thời gian nhanh nhất để Hùng đi đến đích.
Ví dụ:
FESTIVAL.INP
FESTIVAL.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
-----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:.....................................................................................