Đề thi chọn đội tuyển dự thi học sinh giỏi Quốc gia THPT môn Tin học năm 2016 - Sở GD & ĐT Lào Cai

1/3

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ó

ĐỀ CHÍNH THỨC

ThuVienDeThi.com

2/3

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 (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.

ThuVienDeThi.com