De thi chon doi tuyen quoc gia tinh Lao Cai

SỞ GD&ĐT LÀO CAI
KỲ THI CHỌN ĐỘI TUYỂN DỰ THI HSG QUỐC GIA THPT


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ó
đoạn dây xanh,
đoạn dây đỏ,
đoạn dây tím và
đ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
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
. 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
;

Dòng 2 chứa
số nguyên dương là độ dài
đoạn dây xanh
Dòng 3 chứa
số nguyên dương là độ dài
đoạn dây đỏ
Dòng 4 chứa
số nguyên dương là độ dài
đoạn dây tím
Dòng 5 chứa
số nguyên dương là độ dài
đ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á

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ó

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:
, ở đâ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