Đề thi chọn học sinh giỏi lớp 12 THPT môn Tin học - Năm học 2013-2014 - Sở GD&ĐT Ninh Bình (Vòng 2) (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI LỚP 12 THPT 
Kỳ thi thứ nhất - Năm học 2013 – 2014
MÔN: TIN HỌC
Ngày thi 09/10/2013
(Thời gian 180, phút không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
 Tổng quan đề thi:
Bài
Chương trình
Input
Output
Thời gian chạy
1- Dãy số
SUBSEQ.PAS
SUBSEQ.INP
SUBSEQ.OUT
1giây/test
2- Chia và trừ
DIVDEC.PAS
DIVDEC.INP
DIVDEC.OUT
2giây/test
3- Chiến tranh
WAR.PAS
WAR.INP
WAR.OUT
1giây/test
Lưu ý: Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên. 
 Bài 1: Dãy con dài nhất (7,0 điểm)
Yêu cầu: Cho dãy số nguyên dương a1, a2, ...., an trong đó các giá trị ai ≤ M. Hãy tìm dãy con dài nhất của dãy gồm các số hạng liên tục mà trong đó mỗi giá trị xuất hiện không quá K lần.
Dữ liệu vào: Chứa trong file SUBSEQ.INP gồm: 
+ Dòng đầu tiên chứa 3 số N, M, K (1 ≤ N, M ≤ 105)
+ Các dòng tiếp theo chứa n số nguyên dương lần lượt là a1, a2, ..., an. 
(Hai số cạnh nhau trên một dòng cách nhau bởi khoảng trắng).
Dữ liệu ra: Ghi ra file SUBSEQ.OUT một số nguyên là độ dài của dãy con tìm được.
Ví dụ:
SUBSEQ.INP
SUBSEQ.OUT
5 10 2
1 1 1 2 2
4
(60% số test có n ≤ 1000)
Bài 2: Chia và trừ (6,0 điểm)
Cho một dãy số 5 số nguyên không âm sắp xếp trên một vòng tròn. Bạn có hai phép biến đổi dãy số như sau: 
+ Chọn 2 số nguyên dương liên tiếp và chia mỗi số cho 2. Phép chia ở đây chỉ giữ lại phần nguyên của thương (cụ thể: nếu n lẻ thì phép chia sẽ cho kết quả là (n – 1) / 2).
+ Chọn 2 số nguyên dương lẻ liên tiếp, trừ mỗi số  đi 1.
Yêu cầu: tính số cách biến đổi dãy số về dãy 5 số 0.
Dữ liệu vào: Chứa trong file DIVDEC.INP gồm một dòng duy nhất ghi 5 số nguyên dương không vượt quá 30000 tương ứng là 5 phần tử của dãy số.
Dữ liệu ra: DIVDEC.OUT 
ghi ra số cách biến đổi dãy số về dãy 5 số 0 theo modulo 1000000007.
Ví dụ:
DIVDEC.INP
DIVDEC.OUT
DIVDEC.INP
DIVDEC.OUT
1 1 0 0 0
2
1 1 0 1 0
0
(60% số test có các số nguyên ≤ 100)Bài 3: Chiến tranh (7,0 điểm)
Đất nước Bit vừa trải qua một cuộc chiến tranh xâm lược của đội quân Virut, hệ thống giao thông đi lại bị tàn phá nặng nề, vì vậy nhà vua quyết định cải tạo lại hệ thống đường, với mỗi con đường phải trả một chi phí nhất định. Vương quốc gồm có N thành phố đánh số từ 1 đến N và có M con đường hai chiều nối giữa hai thành phố, giữa 2 thành phố có thể tồn tại nhiều hơn 1 con đường. Mạng lưới giao thông được thiết kế sao cho giữa 2 thành phố bất kỳ luôn có đường đi (đường nối trực tiếp hoặc đường qua các thành phố trung gian khác). Nhà vua muốn cải tạo lại hệ thống giao thông sao cho giữa 2 thành phố phải có đường đi (trực tiếp hoặc đi qua thành phố trung gian) và chi phí cải tạo là tối thiểu. Cố vấn tài chính đã đưa ra danh sách các cách cải tạo hệ thống đường giao thông thỏa mãn yêu cầu của nhà vua, khi đó nhà vua chú ý tới những con đường nằm trong tất cả các danh sách cải tạo và cho rằng đó là những con đường quan trọng. 
Yêu cầu: Bạn hãy xác định những con đường quan trọng trong thành phố.
Dữ liệu vào : Chứa trong file WAR.INP có dạng
+ Dòng 1: 2 số nguyên N và M tương ứng là số thành phố và số con đường 
+ M dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương a, b, c có nghĩa là : con đường nối thành phố a và thành phố b có chi phí nâng cấp là c.
Dữ liệu ra : Ghi ra file WAR.OUT có dạng
+ Dòng 1 : Số nguyên x là số lượng con đường quan trọng
+ X dòng tiếp theo, mỗi dòng ghi 2 số a và b nghĩa là con đường nối a và b là con đường quan trọng. Các con đường được liệt kê theo thứ tự từ điển
Hạn chế 1 ≤ n ≤ 50 000 1 ≤ m ≤ 100 000 1 ≤ c ≤ 1 000 000 000
Ví dụ:
WAR.INP 
WAR.OUT
1
2
3
4
1
1
2
2
6
Giải thích
4 5
1 2 1
2 3 2
4 3 1
1 4 2
1 3 6
2
1 2
3 4
Có 2 phương án cải tạo hệ thống giao thông : 1-2, 1-4, 3-4 
 1-2, 2-3, 3-4
Có 2 con đường quan trọng (tồn tại trong cả hai phương án cải tạo) 1-2 và 3-4
(60% số test có n ≤ 100)
---------------------Hết---------------------
Họ và tên thí sinh...................................... Số báo danh:.........................................................
Chữ kí của giám thị 1................................ Chữ kí của giám thị 2............................................