Đề thi HSG 12 môn Tin học (bảng A), tỉnh Đồng Nai, năm 2015 - 2016

Mời các bạn tham khảo
--------

SỞ GIÁO DỤC VÀ ĐÀO TẠO
ĐỒNG NAI
KỲ THI CHỌN HỌC SINH GIỎI LỚP 12
NĂM HỌC 2015-2016
ĐỀ THI CHÍNH THỨC
Môn: Tin học Chuyên.
Thời gian làm bài: 150 phút.
Ngày thi: 22/01/2016
(Đề thi này gồm 02 trang, có 03 câu)
TỔNG QUAN ĐỀ THI
TT TÊN BÀI Tên file chương trình Tên file input Tên file output Điểm
1 MINIMAX MINIMAX.* MINIMAX.INP MINIMAX.OUT 7
2 Làm vườn TREES.* TREES.INP TREES.OUT 7
3 Du lịch 2016 DULICH.* DULICH.INP DULICH.OUT 6
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à Pascal hoặc C++

Bài 1. (7 điểm) MINIMAX – MINIMAX
Cho dãy số



   
. Cho 2 số X,Y, tìm số Z thỏa
-    
- Dãy số




 

 được tính như sau:

 
         
Từ đó ta tìm được K =    



 
 .

Yêu cầu: Tìm Z để K là lớn nhất.
Input:

- Dòng đầu ghi số N là số phần tử của dãy A (       )
- Dòng tiếp theo ghi N số là các phần tử của dãy A (

)
- Dòng thứ ba ghi 2 số X Y cách nhau bởi khoảng trắng. (      

 
)
Output:

- Một dòng duy nhất ghi số Z tìm được. Nếu có nhiều hơn một đáp án thì ghi số Z lớn nhất
thỏa yêu cầu.
Ví dụ:
Input Output
3
5 8 14
4 9
9

Bài 2. (7 điểm) Làm vườn – TREES
Vườn nhà Tèo có trồng một số cây cảnh trong vườn. Mỗi loại cây được đánh ký hiệu ký tự từ a
đến z. Hôm nay là gần đến tết nên Tèo muốn chỉnh đốn lại trật tự các cây trong vườn.
Tèo muốn là mỗi hàng cây trong vườn nhà mình phải được trồng theo một trật tự “siêu đẹp”. Trật
tự “siêu đẹp” của Tèo được định nghĩa như sau: mỗi hàng cây có thể được chia thành 2 đoạn
giống hệt nhau về loại cây, số lượng mỗi loại và trật tự trồng.
Ví dụ: Hàng cây trồng theo thứ tự abab được gọi là hàng cây “siêu đẹp” vì có thể chia thành 2
đoạn ab ab giống hệt nhau. Hàng cây chỉ có một cây không là siêu đẹp.
Với mỗi hàng cây, có thể tìm cách tạo thành hàng cây siêu đẹp bằng cách bỏ bớt một số cây và
giữ nguyên thứ tự các cây còn lại. Ví dụ: hàng cây baaba chưa là hàng cây siêu đẹp nên có thể bỏ
bớt cây thứ 3 baaba.

Yêu cầu: Cho biết hiện trạng của các hàng cây trong vườn, với mỗi hàng hãy cho biết có bao
nhiêu cách để tạo thành hàng cây siêu đẹp.

Input:
- Dòng đầu tiên ghi số T là số hàng cây trong vườn. (      )
- Dòng thứ i trong T dòng tiếp theo: ghi một xâu S cho biết trạng thái của hàng cây thứ i.
(



    )

Output:
- Với hàng cây thứ i xuất ra số cách tạo thành hàng cây siêu đẹp. Số cách có thể rất lớn nên
chỉ cần xuất ra kết quả là số dư khi chia cho
 
Ví dụ:
Giải thích:

- Hàng cây số 1 có 3 cách tạo ra hàng cây siêu đẹp bằng cách bỏ 1
trong 3 cây (aaa,aaa,aaa) để tạo thành hàng cây có 2 cây aa. (tức
là : aaaaa,aaaaa,aaaaa)
- Hàng cây số 2 có 3 cách để tạo thành hàng cây siêu đẹp abab 
aa, abab  bb, abab
- Hàng cây số 3 có 6 cách baabababa, baabababa, baabaaa, baabaaa,
baabaaa, baababb
Bài 3. (6 điểm) Du lịch 2016 – DULICH
Nghỉ hè, thầy chủ nhiệm quyết định cho đội tuyển Tin đến tỉnh X du lịch. Tỉnh có N địa điểm du
lịch đánh số từ 1 đến N được nối với nhau bởi các con đường một chiều. Giữa hai địa điểm chỉ có
nhiều nhất một con đường. Họ phải xuất phát từ khách sạn ở  địa điểm 1 đi theo các con đường
một chiều để đến thăm địa điểm khác và quay trở về địa điểm 1 để nghỉ ngơi. Đội tuyển rất háo
hức muốn thăm nhiều địa điểm khác nhau của thành phố X xinh đẹp, tuy nhiên việc phải đi theo
các con đường một chiều và quay về địa điểm xuất phát khiến số địa điểm bị giới hạn. Vì vậy đội
tuyển đã xin phép thầy được chọn một con đường và đi ngược chiều
đúng một lần với mong muốn sẽ tham quan được nhiều địa điểm hơn.
Tất nhiên thầy cho phép nhưng yêu cầu các bạn phải cho thầy biết số
địa điểm khác nhau được thăm nhiều nhất là bao nhiêu nếu đi theo
cách của các bạn.
Input
 Dòng đầu ghi 2 số nguyên dương N và M, cho biết số lượng
địa điểm và số lượng đường một chiều
(          

).
 M dòng sau, mỗi dòng ghi 2 số nguyên dương X Y mô tả một
con đường một chiều. Từ địa điểm X đến địa điểm Y.
Output: Ghi một số duy nhất cho biết số lượng tối đa các địa điểm
khác nhau đội tuyển có thể tham quan.
Giải thích:
Họ có thể đi theo tuyến đường 1, 2, 4, 7, 2, 5, 3, 1. Họ đi ngược 1 lần ở con đường 3 5.


---- HẾT ----
(Giám thị coi thi không giải thích gì thêm)
Input Output
3
aaa
abab
baaba
3
3
6
Input Output
7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

6