Đề giao lưu đội tuyển HSG lần 1 môn Tin học Lớp 12 - Năm học 2020-2021 - Sở Giáo dục và Đào tạo Thanh Hóa

SỞ GD&ĐT THANH HOÁ
HĐ THI LIÊN TRƯỜNG
ĐỀ THI KHẢO SÁT CHẤT LƯỢNG ĐỘI TUYỂN HỌC SINH GIỎI CẤP TỈNH LỚP 12 LẦN 1 NĂM 2020-2021
Môn thi: Tin học
Thời gian làm bài: 180 phút
Tổng quan bài thi:
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Bài 1
CẮT CHỮ VI TÍNH
BAI1.*
BAI1.INP
BAI1.OUT
Bài 2
NGÔN NGỮ MUMBA
BAI2.*
BAI2.INP
BAI2.OUT
Bài 3
CẶP ĐÔI HOÀN HẢO
BAI3.*
BAI3.INP
BAI3.OUT
Bài 4
TÍNH TỔNG
BAI4.*
BAI4.INP
BAI4.OUT
Bài 5
ĐẾM DÃY CHIA HẾT
BAI5.*
BAI5.INP
BAI5.OUT
Dữ liệu vào là đúng đắn, không cần phải kiểm tra. Các số trên một dòng ghi cách nhau một dấu cách.
Hãy lập trình giải các bài toán sau:
Bài 1. CẮT CHỮ VI TÍNH
Trong kỳ thi học sinh giỏi toàn tỉnh năm 2018, ban tổ chức có ý định in vi tính số báo danh của từng thí sinh, sau đó dán lên từng bàn vi tính để các em biết vị trí ngồi của mình. Chữ số vi tính là các số 0,1,2,3,4,5,6,7,8,9 được in ra trên các miếng đề can và dán được lên mặt bàn. Số báo danh của thí sinh được kết hợp từ các chữ số vi tính đó, ví dụ số báo danh 168 được kết hợp từ 3 chữ số là 1,6, và 8. Số báo danh của thí sinh được đánh từ 1 đến n, trong đó n là số thí sinh tham gia. Số lượng chữ số vi tính được in ra càng nhiều, kinh phí càng lớn, do đó ban tổ chức muốn biết tổng số chữ vi tính sẽ được in ra vừa đủ để sử dụng cho n thí sinh. Ví dụ: nếu có 13 thí sinh tham dự thì các số báo danh cần đánh là 1,2,3,4,5,6,7,8,9,10,11,12,13, như vậy cần dùng đến 17 chữ số vi tính. 
Yêu cầu: hãy giúp ban tổ chức tính toán xem cần in ra bao nhiêu chữ số để đánh số báo danh cho n thí sinh.
Dữ liệu: Vào từ file văn bản BAI1.INP chứa duy nhất một số n (1 ≤ n < 109) là số thí sinh sẽ tham dự kỳ thi. 
Kết quả: Đưa ra file văn bản BAI1.OUT gồm 1 số duy nhất là tổng số chữ số vi tính cần in từ 1 tới n.
Ví dụ:
BAI1.INP
BAI1.OUT
13
17
Bài 2: NGÔN NGỮ MUMBA
Mỗi từ trong ngôn ngữ của bộ tộc Mumba là một xâu kí tự hình thành chỉ từ hai kí tự a và b theo quy tắc sau:
Không chứa 2 kí tự b liên tiếp
Không có ba từ con giống nhau đứng liên tiếp trong một từ, như vậy aaa không phải là một từ Mumba (có 3 từ con a liên tiếp), aabababa cũng không phải là một từ Mumba (có 3 từ con ab liên tiếp), còn aba là một từ Mumba.
Yêu cầu: Cho n xâu kí tự, mỗi xâu chỉ gồm các kí tự chữ cái tiếng anh (‘a’..’z’), có độ dài không quá 25 kí tự. Hãy đếm xem trong n xâu đã cho thì có bao nhiêu xâu là một từ trong ngôn ngữ Mumba.
Dữ liệu vào: vào từ file văn bản BAI2.INP gồm:
Dòng đầu ghi hai số nguyên dương n (n ≤ 100).
N tiếp theo, mỗi dòng ghi một xâu kí tự.
Kết quả: ghi ra file văn bản BAI2.OUT gồm 1 số duy nhất là số lượng từ Mumba đếm được.
BAI2.INP
BAI2.OUT
3
aabababa
cba
abaa
1
Bài 3: CẶP ĐÔI HOÀN HẢO
Nhân dịp năm mới Mậu Tuất 2018, đất nước XYZ muốn tuyển chọn một cặp đôi hoàn hảo để trình diễn màn khiêu vũ tuyệt đẹp vốn là văn hóa lâu đời của đất nước.
Một cặp đôi được gọi là hoàn hảo nếu cặp đôi đó có cả nam và nữ, chênh lệch chiều cao của hai người không được vượt quá K milimet và chiều cao của người nữ không được cao hơn người nam.
Đất nước đã tuyển chọn được N vũ công gồm cả nam và nữ và muốn biết có bao nhiêu cách để chọn ra đúng một cặp đôi hoàn hảo.
Yêu cầu: Tính xem có bao nhiêu cách để chọn ra đúng một cặp hoàn hảo, hai cặp khác nhau nếu có ít nhất 1 người được chọn ở cặp này mà không được chọn ở cặp kia.
Dữ liệu vào: vào từ file văn bản BAI3.INP gồm:
Dòng đầu ghi hai số nguyên dương N, K (N ≤ 105; K ≤ 500).
Dòng tiếp theo ghi N số là chiều cao hi của vũ công thứ i.
Quy ước hi > 0 nếu đó là vũ công nam và hi ≤ 0 nếu là nữ. |hi| ≤ 2000
Kết quả: ghi ra file văn bản BAI3.OUT gồm 1 số duy nhất là số lượng cách có thể chọn được.
Ví dụ:
BAI3.INP
BAI3.OUT
4 2
1600 -1601 -1602 1603
4
Rằng buộc:
Có 50% số test ứng với 50% số điểm của bài có N ≤ 104.
Có 50% số test ứng với 50% số điểm của bài có 104 ≤ N và số vũ công nam không quá 104.
Bài 4. TÍNH TỔNG
Sau buổi học về số học, Minh đã biết cách tính tổng của n số tự nhiên liên tiếp. Ở nhà, Minh tiếp tục làm các bài tập về tính tổng của các số tự nhiên liên tiếp. Minh thắc mắc, liệu với số tự nhiên K thì có thể phân tích K thành tổng các số tự nhiên liên tiếp hay không?. Ví dụ với K = 9 (có thể phân tích: 9 = 9; 9 = 5+4; 9 = 2 + 3 + 4) thì có 3 cách phân tích thành tổng các số tự nhiên liên tiếp.
Yêu cầu: Viết chương trình giúp Minh tìm số cách phân tích số nhiên K thành tổng các số tự nhiên liên tiếp.
Dữ liệu vào: Từ file văn bản BAI4.INP một dòng duy nhất chứa số nguyên dương K (K ≤ 1012).
Kết quả: Ghi ra file BAI4.OUT một số duy nhất là số cách phân tích tìm được.
Ví dụ:
BAI4.INP
BAI4.OUT
9
3
Ràng buộc:
Có 1/3 số test ứng với 1/3 số điểm của bài có K ≤ 107;
Có 2/3 số test còn lại ứng với 2/3 số điểm của bài có 107 < K ≤ 1012.
Bài 5. ĐẾM DÃY CHIA HẾT
Cho một dãy số nguyên dương, yêu cầu hãy đếm số lượng dãy con liên tiếp có tổng chia hết cho . Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hai dãy con đó trong dãy đã cho là khác nhau. Ví dụ với , dãy: có 4 dãy con thỏa mãn là . Với và dãy: (1, 1, 1, 1) thì có 4 dãy con thỏa mãn.
Dữ liệu: Vào từ file văn bản BAI5.INP gồm 2 dòng:
Dòng đầu là 2 số nguyên dương d và N (d ≤ 106, N ≤ 105)
Dòng thứ 2 chứa N số nguyên dương biểu diễn dãy số, các số trong dãy không quá 109. 
Kết quả: Ghi ra file văn bản BAI5.OUT gồm 1 số duy nhất là kết quả tìm được.
Ví dụ
BAI5.INP
BAI5.OUT
4 6
2 1 2 1 4 1
4
Rằng buộc:
Có 1/3 số test tương ứng với 1/3 số điểm có N ≤ 103
Có 2/3 số test tương ứng với 2/3 số điểm có 103 < N ≤ 105
Cán bộ coi thi không giải thích gì thêm.
----------------------------- Hết -----------------------------