Kỳ thi chọn đội tuyển dự thi học sinh giỏi quốc gia THPT năm 2016 môn: Tin Học

SỞ GD&ĐT LÀO CAI
KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HSG QUỐC GIA THPT
ĐỀ CHÍNH THỨC
NĂM 2016
Môn: TIN HỌC
Thời gian: 180 phút (Không kể thời gian giao đề)
Ngày thi: 20/10/2015
(Đề thi gồm 03 trang)
TỔNG QUAN VỀ BÀI THI
Tên bài
File chương trình
File vào
File ra
Nối dây
TERA.*
TERA.INP
TERA.OUT
Số nguyên tố
PRIME.*
PRIME.INP
PRIME.OUT
Hành trình du lịch
TOUR.*
TOUR.INP
TOUR.OUT
Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình tường ứng là Pascal hoặc C++ . Hãy lập trình giải các bài toán sau:
Bài 1: (6 điểm) Nối dây
Đề thi vào trường mẫu giáo SuperBabies khá đơn giản: Có n đoạn dây xanh, n đoạn dây đỏ, n đoạn dây tím và n đoạn dây vàng. Độ dài các đoạn dây được cho trước.
Mỗi bé được cho một số nguyên L và cần cho biết có bao nhiêu cách chọn đúng 1 đoạn dây xanh, 1 đoạn dây đỏ, 1 đoạn dây tím và 1 đoạn dây vàng để nối lại thành một sợi dây trang trí có độ dài bằng L. Hai cách chọn được gọi là khác nhau nếu có đoạn dây được chọn trong một cách nhưng không được chọn trong cách còn lại.
Yêu cầu: Viết chương trình tìm đáp án để chấm cho các bé.
Dữ liệu: Vào từ file văn bản TERA.INP
Dòng 1 chứa hai số nguyên dương n≤1000; L≤109
Dòng 2 chứa n số nguyên dương là độ dài n đoạn dây xanh
Dòng 3 chứa n số nguyên dương là độ dài n đoạn dây đỏ
Dòng 4 chứa n số nguyên dương là độ dài n đoạn dây tím
Dòng 5 chứa n số nguyên dương là độ dài n đoạn dây vàng
Các số trên một dòng của input file được ghi cách nhau bởi dấu cách, độ dài các đoạn dây không quá 109
Kết quả: Ghi ra file văn bản TERA.OUT một số nguyên duy nhất là số cách chọn tính được
Ví dụ:
TERA.INP
TERA.OUT
3 28
1 1 1
1 1 1
10 11 12
13 14 15
18
Chú ý: Có ít nhất 40% số điểm ứng với các test có n≤50
Bài 2. Số nguyên tố
Cho dãy số nguyên x1, x2, , xN và hàm f(p) là số lượng các phần tử thuộc dãy x chia hết cho p.
Cho M truy vấn, mỗi truy vấn cho hai số nguyên li, ri. Bạn phải trả lời câu hỏi: Tính tổng: p∈S(li,ri)Mf(p), ở đây S(li, ri) là tập các số nguyên tố thuộc đoạn [li,ri]. 
INPUT: 
Dòng đầu tiên chứa giá trị N (1 ≤ N ≤ 106)
Dòng hai chứa N số nguyên x1, x2, , xN (2 ≤ xi ≤ 105)
Dòng ba chứa giá trị M (1 ≤ M ≤ 5.104)
M dòng tiếp theo, mỗi dòng chứa hai số li, ri (2 ≤ li ≤ ri ≤ 2.109)
OUTPUT:
Gồm M dòng, mỗi dòng là câu trả lời của truy vấn tương ứng của INPUT.
Ví dụ:
PRIME.INP
PRIME.OUT
6
5 5 7 10 14 15
3
2 11
3 12
4 4
9
7
0
Giải thích:
Tại truy vấn 1: l = 2, r = 11: 
Ta cần tính f(2) + f(3) + f(5) + f(7) + f(11) = 2 + 1 + 4 + 2 + 0 = 9.
Tại try vấn 2: l = 3, r = 12:
Ta cần tính f(3) + f(5) + f(7) + f(11) = 1 + 4 + 2 + 0 = 7
Tại truy vấn 3: l = 4, r = 4: không có số nguyên tố nào thuộc đoạn [l,r], nên kết quả truy vấn bằng 0
* Chú ý:
40% test 1 ≤ N, M ≤ 100; 1 ≤ li ≤ ri ≤ 1000
40% test tiếp theo 1 ≤ N, M ≤ 1000; 1 ≤ li ≤ ri ≤ 1000
20% test còn lại 1 ≤ N ≤ 106, 2 ≤ xi ≤ 105, 1 ≤ M ≤ 5.104, 2 ≤ li ≤ ri ≤ 2.109
Bài 3: Hành trình du lịch 
Công ty du lịch LCTRAVEL chuyên tổ chức các hành trình du lịch trong vùng lãnh thổ gồm điểm du lịch trọng điểm, được đánh số từ 1 đến n. Hệ thống giao thông trong vùng gồm m (m ≤ n(n-1)) tuyến đường một chiều khác nhau, tuyến đường thứ j (j = 1, 2, ... , m) cho phép đi từ địa điểm uj đến địa điểm vj với chi phí đi lại là số nguyên dương c(uj,vj). Công ty vừa nhận được một hợp đồng yêu cầu xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm du lịch s1, s2, ..., sk (sp ≠1 với p = 1, 2, ..., k) sau đó quay về địa điểm du lịch 1 với tổng chi phí (được tính như là tổng chi phí của các tuyến đường mà hành trình đi qua) nhỏ nhất. 
Yêu cầu: Cho thông tin về hệ thống giao thông và k địa điểm du lịch s1, s2, ..., sk. Hãy xây dựng một hành trình du lịch xuất phát từ địa điểm du lịch 1 và đi thăm k địa điểm du lịch s1, s2, ..., sk sau đó quay về địa điểm du lịch 1 với tổng chi phí nhỏ nhất. 
Dữ liệu: Vào từ file văn bản TOUR.INP theo khuôn dạng sau: 
Dòng thứ nhất chứa ba số nguyên dương n, m và k; 
Dòng thứ hai chứa k số nguyên dương 	. 
Dòng thứ trong số dòng tiếp theo chứa ba số nguyên dương cho biết thông tin về tuyến đường thứ . Giả thiết là uj≠vj; c(uj,vj) ≤ 109 với 
Kết quả: Ghi ra file văn bản TOUR.OUT một số nguyên là tổng chi phí nhỏ nhất tìm được. Qui ước: Ghi số -1 nếu không tìm được hành trình du lịch thoả mãn yêu cầu. 
Ví dụ: 
TOUR.INP 
TOUR.OUT 
Hình minh hoạ 
6 8 2 
2 5 
1 2 4 
2 4 2 
4 3 3 
3 1 4 
4 1 5 
3 5 5 
5 3 1 
5 6 7 
19 
Ràng buộc: 
Có 50% số test ứng với 50% số điểm của bài có và . 
Có 50% số test khác ứng với 50% số điểm còn lại của bài có và 
------------Hết-----------
Họ tên thí sinh:.
SBD:.
Giám thị số 1:....
Giám thị số 2:....
Ghi chú : - Thí sinh không được sử dụng tài liệu
 - Cán bộ coi thi không giải thích gì thêm