Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học lớp 12 năm học 2017 - 2018 Sở GD&ĐT Hưng Yên

VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
SỞ GIÁO DỤC ĐÀO TẠO
HƯNG YÊN
ĐỀ CHÍNH THỨC
(Đề thi gồm 02 trang)
KỲ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH
NĂM HỌC 2017 2018
Môn thi: TIN HỌC
Thời gian m bài: 180 phút (không kể thời gian phát đề)
Tổng quan v các bài thi
Tên bài
Tên file chương trình
File dữ liệu vào
File kết quả
Bài 1
Tính tổng
SUMX.*
SUMX.INP
SUMX.OUT
Bài 2
Bán hàng qua mạng
SORT.*
SORT.INP
SORT.OUT
Bài 3
Hoán vị
JOSEPHUS.*
JOSEPHUS.INP
JOSEPHUS.OUT
Chú ý: Dấu * trong tên file chương trình được thay thế bởi PAS hoặc CPP tùy theo ngôn ngữ
sử dụng PASCAL hoặc C++
Hãy lập trình giải các i toán sau:
Bài 1: Tính tổng (7 điểm).
Cho dãy số gồm N s nguyên dương a
1
, a
2
, …, a
N
giá trị K. Hãy đếm các cặp phần tử
a
i
+ a
j
= K (i < j).
Dữ liệu vào: cho bởi File SUMX.INP gồm hai dòng:
ng đầu tiên ghi giá trị N và K (2 N 10
5
, K 10
5
).
ng hai ghi giá trị của dãy a
1
, a
2
, …, a
N
(1 a
i
10
5
).
Kết quả: ghi ra file SUMX.OUT số ợng cần tìm.
dụ:
SUMX.INP
4 10
9 1 9 9
9 10
6 7 1 3 5 3 4 7 9
Giới hạn:
80% số test có 2 N 1000.
20% test n lại ứng với 1000 < N 100000.
Bài 2: Bán hàng qua mạng (7 điểm)
Trang một học sinh THPT trường X. một học sinh nhưng em sở thích niềm
đam trong lĩnh vực kinh doanh qua mạng. Mặt hàng em bán bút bi. Qua một thời gian
kinh doanh, đơn hàng ngày càng tăng, s lượng bút bi nhập về ngày càng nhiều. Để thể
nhanh chóng giao hàng cho khách, Trang muốn sắp xếp những chiếc bút theo màu sắc. Trang
dãy bút bi gồm c màu xanh, tím, hồng. số lượng bút rất lớn không nhiều thời
gian nên Trang muốn nhờ các bạn học sinh giỏi bộ môn Tin học tham gia kỳ thi chọn học sinh
giỏi cấp tỉnh năm 2018 sắp xếp giúp. Em hãy giúp Trang sắp xếp lại y bút bi theo quy luật
Xanh - Hồng - m.
Dữ liệu vào: Cho bởi file SORT.INP gồm 2 dòng:
Dòng 1: Ghi số N là số lượng bút bi (1 N 10
6
).
Dòng 2: Gồm N tự tả dãy bút bi ( X Xanh, T Tím, H Hồng), các u được
phân cách nhau bởi một dấu cách.
VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí
Kết quả: Ghi ra file SORT.OUT kết quả của dãy sau khi đã được sắp xếp đúng thứ tự, các
tự được phân cách bởi một dấu cách.
SORT.INP
SORT.OUT
4
X T H X
X X H T
10
X H X X X H X X X X
X X X X X X X X H H
Giới hạn:
60% số test có 1 N 1000.
20% test n lại ứng với 1000 < N 100000.
20% test n lại ứng với 100000 < N 1000000.
Bài 3: Hoán vị (6 điểm)
Tương truyền rằng Josephus bốn mươi chiến bị người La Mã bao vây trong một
hang động. Họ quyết định tự vẫn chứ không chịu bị bắt. 41 người đứng thành vòng tròn bắt
đầu đếm theo một chiều vòng tròn, cứ người o đếm đến 3 thì phải tự vẫn người kế tiếp
bắt đầu đếm t 1. Josephus không muốn chết đã chọn được một vị trí ông ta cùng với
một người nữa hai người sống sót cuối cùng theo quy luật này. Hai người sống sót sau đó đã
đầu hàng và gia nhập quân La (Josephus sau đó chỉ nói rằng đó sự may mắn, hay “bàn
tay của Chúa mới giúp ông và người kia sống sót).
rất nhiều truyền thuyết tên gọi khác nhau v bài toán Josephus. Trong toán học,
người ta phát biểu bài toán dưới dạng một trò chơi: Cho n người đứng quanh vòng tròn theo
chiều kim đồng hồ đánh số từ 1 đến n. Họ bắt đầu đếm từ người thứ nhất theo chiều kim đồng
hồ, người nào đếm đến m (m < n) thì bị loại khỏi vòng người kế tiếp bắt đầu đếm từ 1. Trò
chơi tiếp diễn cho tới khi vòng tròn chỉ còn lại 1 người. Nếu ta xếp số hiệu của n người này
theo thứ tự họ bị loại khỏi vòng sẽ được một hoán vị (j
1
, j
2
, , j
n
) của dãy số (1,2, n) gọi
hoán vị Josephus(n,m)
dụ với n = 7, m = 3, hoán vị Josephus sẽ (3,6,2,7,5,1,4). Bài toán đặt ra cho
trước hai số n, m hãy xác định hoán vị Josephus(n,m).
Dữ liệu vào: Cho bởi file JOSEPHUS.INP gồm:
Hai số nguyên dương n, m 10
5
.
Kết quả: Ghi ra file JOSEPHUS.OUT gồm:
Hoán vị Josephus(n,m), mỗi số phân cách nhau bởi một dấu cách.
JOSEPHUS.INP
JOSEPHUS.OUT
7 3
3 6 2 7 5 1 4
12 3
3 6 9 12 4 8 1 7 2 11 5 10
Giới hạn:
60% số test có 1 N 100.
20% test n lại ứng với 100 < N 10000.
20% test n lại ứng với 10000 < N 100000.
-------------- HẾT --------------
Xem thêm bài tiếp theo tại: https://vndoc.com/tai-lieu-hoc-tap-lop-12

Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học lớp 12

VnDoc xin giới thiệu tới bạn đọc tài liệu Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học lớp 12 năm học 2017 - 2018 Sở GD&ĐT Hưng Yên, tài liệu gồm 3 bài toán tự luận, thời gian làm bài 180 phút. Mời thầy cô cùng các bạn học sinh tham khảo.

---------------------------------------------

Trên đây VnDoc.com đã giới thiệu tới bạn đọc tài liệu: Đề thi chọn học sinh giỏi cấp tỉnh môn Tin học lớp 12 năm học 2017 - 2018 Sở GD&ĐT Hưng Yên. Để có kết quả cao hơn trong học tập, VnDoc xin giới thiệu tới các bạn học sinh tài liệu Thi thpt Quốc gia môn Toán, Thi thpt Quốc gia môn Hóa học, Thi thpt Quốc gia môn Vật Lý, Thi thpt Quốc gia môn Sinh họcVnDoc tổng hợp và đăng tải.

Đánh giá bài viết
5 4.625
Sắp xếp theo

Môn khác lớp 12

Xem thêm