- Trang chủ >>
- Đề thi >>
- Đề thi lớp 12
Bộ đề thi chọn HSG môn Tin số 02
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (167.39 KB, 15 trang )
ĐỀ KHẢO SÁT ĐỘI TUYỂN HSG 06
Môn thi: Tin học
Thời gian: .... phút (không kể thời gian giao đề)
Đề này có 05 câu, gồm 03 trang.
Bài
1
2
3
4
5
Tên bài
Pha Cocktail
Trị chơi
Thừa số nguyên tố
Xâu con
Đối xứng cặp
File chương trình
BAI1.*
BAI2.*
BAI3.*
BAI4.*
BAI5.*
File dữ liệu vào
BAI1.INP
BAI2.INP
BAI3.INP
BAI4.INP
BAI5.INP
File kết quả
BAI1.OUT
BAI2.OUT
BAI3.OUT
BAI4.OUT
BAI5.OUT
Bài 1. (6 điểm) Pha Cocktail
Trong nhà Linh có một ít nước cam, táo và dứa. Cơ ta quyết định tạo ra một loại
Cocktail theo từ ba loại nước trên theo một cơng thức tìm được trên Intenet. Tỷ lệ các loại
phải được tuân thủ nghiêm ngặt và lượng cocktail là nhiều nhất có thể. Hỏi rằng sau khi pha
cocktail khối lượng của mỗi loại nước còn lại là bao nhiêu?
Input: Từ tệp BAIF1.INP Gồm 2 dịng:
-
Dịng 1: có 3 số nguyên A, B, C lần lượt là khối lượng nước cam, táo và dứa hiện có.
Dịng 2: có 3 số p, q, r là tỷ lệ pha cocktail của mỗi loại (p đơn vị nước cam pha với q đơn vị
nước táo và r đơn vị nước dứa). (A,B,C,p,q,r≤109)
Output: Ghi ra file BAI1.OUT Gồm 3 số thực với 6 chữ số phần thập phân mô tả lượng nước
cam, táo, dứa cịn lại sau khi pha.
Ví dụ:
BAI1.INP
10 15 18
341
BAI1.OUT
0.000000 1.666667 14.666667
Bài 2. (5 điểm) Trò chơi
Phần chơi giành cho khán giả giữa một chương trình truyền hình có nội dung như sau:
một khán giả được chọn làm người chơi và được tặng n đồng (1 ≤ n ≤ 10 16). Nội dung trò
chơi giữa khán giả được chọn (người chơi) với người dẫn chương trình như sau: Gọi số tiền
hiện tại người chơi đang có là k đồng. Nếu k chẵn thì người chơi phải đưa cho người dẫn
chương trình một nửa số tiền mình có, trong trường hợp ngược lại người chơi nhận được
thêm 2k+1 đồng. Sau mỗi lần, người chơi quyết định có tiếp tục chơi hay dừng trò chơi. Trò
chơi cũng kết thúc khi người chơi chỉ còn 1 đồng.
Yêu cầu: Hãy xác định số tiền lớn nhất người chơi có thể nhận được nếu biết cách dừng trò
chơi đúng lúc.
Input: Tệp BAI2.INP gồm một dòng duy nhất chứa số nguyên n
Output: Ghi ra BAI2.OUT một số là kết quả tìm được.
Ví dụ:
BAI2.INP
11
BAI2.OUT
11
52
Bài 3. (4 điểm) Thừa số nguyên tố
Với mọi số ngun dương đều có thể được phân tích ra thừa số ngun tố. Chính vì
vậy, một số ngun dương cịn có thể được xác định bằng một dãy số mơ tả số lần xuất hiện
các số nguyên tố trong phân tích của nó ra thừa số ngun tố. Chẳng hạn số 1650 có thể được
xác định bởi dãy 1 1 2 0 1 vì 1650=21.31.52.70.111
Cho trước số nguyên dương N (1
Dữ liệu: Vào từ file văn bản BAI3.INP gồm một dòng chứa số N
Kết quả: File văn bản BAI3.OUT gồm nhiều dòng lần lượt ghi số lần xuất hiện của các thừa
số nguyên tố (theo thứ tự từ số nguyên tố nhỏ đến số nguyên tố lớn)
Ví dụ:
BAI3.INP
BAI3.OUT
5
3
1
1
Bài 4. (3 điểm) Xâu con
Cho xâu s (độ dài khơng vượt q 106) chỉ gồm hai kí tự ‘A’ và ‘B’. Đếm số cách chọn
cặp chỉ số (i,j) mà xâu con liên tiếp từ kí tự thứ i đến kí tự thứ j của xâu s có số lượng kí tự
‘A’ bằng số lượng kí tự ‘B’.
Dữ liệu: Từ file văn bản BAI4.INP: Chỉ một dòng chứa xâu s.
Kết quả: File văn bản BAI4.OUT: Chỉ một dòng chứa một số là kết quả của bài tốn
Ví dụ:
BAI4.INP
BAI4.OUT
ABAB
4
Bài 5. (2 điểm) Đối xứng cặp
Số nguyên dương x được gọi là số đối xứng cặp nếu: hai chữ số đầu tiên từ phải qua
trái bằng hai chữ số đầu tiên từ trái qua phải. Ví dụ: các số 5,66,131,1221 là số đối xứng cặp;
các số 12,31,57,1231 không phải là số đối xứng cặp
Yêu cầu: Hãy đếm số lượng các số đối xứng cặp trong đoạn [L;R]
Input: Từ tệp văn bản BAI5.INP gồm 1 dòng chứa hai số nguyên dương L và R.
Output: Ghi ra tệp BAI5.OUT số lượng các số đối xứng cặp trong đoạn [L;R]
Ràng buộc:
-
BAI5.INP
BAI5.OUT
10 135
13
Có 60% số thỏa mãn điều kiện 1≤L≤R<106
Có 40% số thỏa mãn điều kiện 106≤L≤R≤1018
--- HẾT ---
22
ĐỀ KHẢO SÁT ĐỘI TUYỂN HSG 07
Môn thi: Tin học
Thời gian: .... phút (không kể thời gian giao đề)
Đề này có 05 câu, gồm 02 trang.
Tổng quan bài thi:
Tên bài
Bài 1
Beauty
Bài 2
Train
Bài 3
Số nhỏ nhất
Bài 4
Tìm số
Bài 5
Thuê máy
File chương trình
BAI1.*
BAI2.*
BAI3.*
BAI4.*
BAI5.*
Dữ liệu vào
BAI1.INP
BAI2.INP
BAI3.INP
BAI4.INP
BAI5.INP
Kết quả ra
BAI1.OUT
BAI2.OUT
BAI3.OUT
BAI4.OUT
BAI5.OUT
Điểm
6
5
4
3
2
- Dấu (*) trong tên file chương trình biểu thị đi file tùy thuộc vào NNLT sử dụng ('pas' đối
với NNLT PASCAL, ‘c’ đối với NNLT C,...).
Bài 1 (6 điểm): BEAUTY
Một số được gọi là đẹp nếu tổng bình phương các chữ số của nó (trong dạng biểu diễn
thập phân) là một số nguyên tố.
Ví dụ: 12 là một số đẹp vì 12 + 22 = 5 là số nguyên tố.
Các số đẹp được đánh số theo thứ tự tăng dần của giá trị, bắt đầu từ 1 trở đi.
Yêu cầu: Cho số nguyên N (1 ≤ N ≤ 106). Hãy tìm số đẹp thứ N.
Dữ liệu: Vào từ file BAI1.INP
Gồm nhiều tests, mỗi test cho trên một dòng chứa một số nguyên N.
Kết quả: Ghi ra file BAI1.OUT
Mỗi test đưa ra trên một dòng là kết quả số đẹp tìm được tương ứng của mỗi test từ file
dữ liệu vào.
Ví dụ:
BAI1.INP
BAI1.OUT
1
11
6
23
Bài 2 (5 điểm): TRAIN
Thành phố đang xây dựng tuyến đường sắt trên cao phục vụ giao thơng nội đơ. Tuyến
đường sẽ có k+1 ga đánh số từ 0 đến k theo đường thẳng. Tàu chạy suốt ngày đêm, từ ga 0
đến ga k và quay lại. Thời gian đi từ một ga tới ga kế tiếp là 1 phút, thời gian dừng ở mỗi ga
là không đáng kể.
Yêu cầu: Nếu một người bước lên tàu ở ga số 0, sau t phút thì xuống tàu. Hỏi người đó
xuống tàu ở ga số mấy?
Dữ liệu: Vào từ file BAI2.INP gồm một dòng chứa 2 số nguyên k và t (0 < k, t ≤ 10 9).
Các số ghi cách nhau một dấu cách.
Kết quả: Đưa ra file văn bản BAI2.OUT gồm một số nguyên là kết quả tìm được
Ví dụ:
BAI2.INP
BAI2.OUT
5 8
2
Bài 3 (4 điêm): Số nhỏ nhất
33
Một số nguyên dương N rất lớn có thể được cho bởi P (P<=20) số nguyên dương A1, A2,
…,Ap và P xâu ký tự S1, S2,...,Sp chỉ gồm các số thập phân bằng cách viết S 1 liên tiếp A1 lần
rồi viết S2 liên tiếp A2 lần,..., viết Sp liên tiếp Ap lần.
Yêu cầu: Giả sử với số N được cho như trên và cho trước số nguyên dương k nhỏ hơn số
chữ số của N. Hãy tìm cách gạch đi k chữ số của N để nhận được một số có giá trị nhỏ nhất .
Dữ liệu: Vào từ file văn bản có tên BAI3.INP gồm:
- Dịng 1: Chứa 2 số nguyên dương P và k phân cách bởi dấu cách
- Dòng 2: Gồm P số nguyên dương A1, A2,…., An cách nhau dấu cách (ai<=100)
- P dòng còn lại: Dòng i chứa xâu Si (độ dài các xâu không vượt quá 255)
Kết quả: Ghi ra file BAI3.OUT là số nhỏ nhất thu được sau khi xố
Ví dụ:
BAI3.INP
BAI3.OUT
3 11
44
342
123
0
45
Bài 4(3 điểm): Tìm số
Hàm Rev(x) được xác định bằng cách đảo ngược thứ tự các chữ số trong x. Cho dãy số
nguyên được xác định như sau:
- A1= 1
- An= Rev(An-1) + 2
Vậy dãy A gồm các số: 1 3 5 7 9 11 13 33…..
Yêu cầu: Cho số nguyên dương N. Hãy xác định số thứ N của dãy
Dữ liệu: Tệp BAI4.INP gồm
- Dòng duy nhất chứa số nguyên dương N (1<=N<=1012)
Kết quả: Tệp BAI4.OUT gồm
- Dòng duy nhất chứa số thứ N tìm được
Ví dụ:
BAI4.INP
BAI4.OUT
2
3
Bài 5 (2 điểm): Thuê máy
Tại thời điểm 0, ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê sử
dụng của N khách. Các khách hàng được đánh số từ 1 đến N. Khách hàng i cần sử
dụng máy từ thời điểm di đến thời điểm Ci (Di và Ci là các số nguyên và 0
khoảng thời gian sử dụng máy tính của hai khách hàng được nhận phục vụ bất kì khơng giao
nhau và tổng tiền thu được từ phục vụ là lớn nhất.
Dữ liệu vào: vào file văn bản BAI5.INP.
- Dòng đầu ghi số N (0
- Dòng thứ i trong N dòng tiếp theo ghi 3 số Di, Ci, Pi cách nhau bởi dấu cách,
i=1,2,..,N
Kết quả ra: Ghi ra file văn bản BAI5.OUT hai số nguyên dương theo thứ tự là số lượng
khách hàng nhận được phục vụ và tổng tiền thu được.
Ví dụ:
BAI5.INP
BAI5.OUT
3
2 180
150 500 150
1 200 100
400 800 80
----------------------------- Hết -----------------------------
55
ĐỀ KHẢO SÁT ĐỘI TUYỂN HSG 08
Môn thi: Tin học
Thời gian: .... phút (không kể thời gian giao đề)
Đề này có 05 câu, gồm 03 trang.
Tổng quan bài thi:
Bài
Tên bài
File chương trình
File dữ liệu vào
File kết quả
1 Kết nối
BAI1.*
BAI1.INP
BAI1.OUT
2 Trồng cây
BAI2.*
BAI2.INP
BAI2.OUT
3 Số lớn nhất
BAI3.*
BAI3.INP
BAI3.OUT
4 Thỏ lạc đường
BAI4.*
BAI4.INP
BAI4.OUT
5 Chia nhóm
BAI5.*
BAI5.INP
BAI5.OUT
Hãy lập trình giải các bài tốn sau:
Bài 1: (6 điểm) Kết nối
An và Thư là hai bạn thân học chung một lớp. Cả hai bạn cùng u thích mơn Tin và
cùng có một biệt tài ghép số rất nhanh. Ngày chủ nhật tuần trước, lớp An và Thư tổ chức đi
dã ngoại. Ban cán sự lớp chia lớp thành hai nhóm chơi trị thách đố với nhau. Nếu nhóm nào
thắng sẽ được thưởng mỗi bạn một vé xem phim với tựa đề “Cô gái năm ấy chúng ta cùng
theo đuổi”, phim dựa trên tiểu thuyết cùng tên của Cửu Bả Đao với nam diễn viên điển trai
thủ vai Kha Cảnh Đằng mà cả An và Thư đều rất yêu thích. An và Thư cùng là trưởng nhóm
của mỗi nhóm. Nhóm An thách đố bài tốn cho nhóm Thư với nội dung như sau:
Từ N số nguyên dương cho trước A1, A2, ..., An (2≤ N≤ 100), mỗi số không vượt quá
9
10 , hãy tạo ra một số mới bằng cách kết nối các số đã cho viết liên tiếp nhau để tạo thành một
số lớn nhất trong tất cả các số được kết nối theo quy tắc trên.
Yêu cầu: Bạn hãy giúp nhóm Thư đưa ra được số lớn nhất theo yêu cầu của nhóm An.
Input: Vào từ file văn bản BAI1.INP
• Dịng 1: Ghi số N (2≤ N≤ 100)
• Từ dòng thứ hai trở đi ghi N số nguyên dương A1, A2, ..., An ( 0
Output: Ghi vào file văn bản BAI1.OUT
- Ghi số lớn nhất được kết nối thành từ các số ban đầu.
Ví dụ:
BAI1.INP
BAI1.OUT
574321
5
1 3 4 57 2
Bài 2: (5 điểm) Trồng cây
Vườn nhà An trồng 2 hàng cây cau tiến vua song song với nhau (ta gọi là hàng cây A
và hàng cây B). Mỗi cây trong một hàng cách nhau 2m và khoảng cách giữa 2 hàng cây là
5m. Các cây ở 2 hàng lần lượt phải trả cơng chăm sóc là: �1, �2, … , �n và �1, �2, … , �n. Biết
cơng chăm sóc được tính theo cặp tương ứng là |�i-bi |. Một ngày nắng đẹp, An muốn thay đổi
vị trí của các cây ở hàng B sao cho tổng cơng chăm sóc 2 hàng cây là ít nhất. Bạn hãy giúp
An việc này.
Input: vào từ file BAI2.INP
66
-Dòng đầu chứa số nguyên dương � (� ≤ 105);
-Dòng thứ hai gồm một dãy số nguyên là công chăm sóc của mỗi cây hàng A: �1, �2,
… , �n (|�i |≤ 105);
- Dòng thứ ba gồm một dãy số ngun là cơng chăm sóc của mỗi cây hàng B: �1, �2,
… , �n (|�i | ≤ 105).
Output: ghi vào file BAI2.OUT một số nguyên duy nhất là tổng tiền
công ít nhất phải trả để chăm sóc 2 hàng cây.
Ví dụ:
BAI2.INP
BAI2.OUT
5
11
32451
09672
Bài 3: (4 điểm) Số lớn nhất
Dãy Fibonaci, dãy số nguyên tố, dãy các số hoàn hảo, dãy các số chính phương… là
những dãy số quen thuộc với An trong suốt cả 12 tháng học đội tuyển Tin học. Sắp đến ngày
thi, An nghĩ mình sẽ thử tạo ra một dãy số mang tên Vắc-xin để nhớ về kỉ niệm của kì thi đặc
biệt đã phải hỗn vì dịch bệnh.
Dãy Vắc-xin được xây dựng như sau:
• V[0] = 0
• V[1] = 1
• V[2i] = V[i]
• V[2i+1] = V[i] + V[i+1]
Tuy nhiên, để Vắc-xin phát huy tác dụng tốt nhất, An phải tìm được giá trị lớn nhất của
dãy Vắc-xin từ 1 đến N. Hãy giúp An thực hiện việc này.
Input: từ file BAI3.INP: - Dòng đầu tiên là số T (<=105).
- T dòng sau, mỗi dòng là 1 số N (N<=105).
Output: ghi vào file BAI3.OUT: T dòng tương ứng với giá trị lớn nhất của các đoạn.
Ví dụ:
BAI3.INP
BAI3.OUT
2
3
5
4
10
Bài 4: (3 điểm) Thỏ lạc đường
An nuôi một chú thỏ con rất dễ thương, một hôm thỏ cute bị lạc đường. Để về được
nhà, thỏ cute cần băng qua một đoạn đường dài N mét, nó có ba cách nhảy với các độ dài
bước nhảy là 3 mét, 2 mét, 1 mét. Một cách đi đúng của thỏ là dãy các bước nhảy của nó có
tổng độ dài bằng n và bước nhảy liền sau không dài hơn bước nhảy liền trước trong dãy bước
nhảy của nó.
77
Yêu cầu: Cho biết số nguyên dương N (1 ≤ N ≤ 1015), hãy tính số cách đi đúng khác nhau của
thỏ để đi hết đoạn đường N mét. Số cách đi có thể rất lớn nên kết quả in ra được viết dưới
dạng số dư của phép chia kết quả cho 1000000.
Input: từ file BAI4.INP, gồm một dòng chứa số nguyên N.
Output: ghi vào file BAI4.OUT, một số nguyên duy nhất là số cách đi đúng của thỏ viết
dưới dạng số dư của kết quả chia cho 1 000 000.
Giới hạn:
40% test đầu tiên có N ≤ 103;
30% test tiếp theo có 103
BAI4.INP
BAI4.OUT
6
7
Bài 5: (2 điểm) Chia nhóm
Đàn bị của nhà bạn An có sở thích là hay đi khám phá những vùng xung quanh nơng
trang. Ban đầu có tất cả N con bị tập trung thành một nhóm và cùng bắt đầu chuyến đi trên
một con đường, cho đến khi gặp một ngã ba đường thì chúng đơi khi chọn cách chia làm 2
nhóm nhỏ hơn (mỗi nhóm ít nhất 1 con bị) và mỗi nhóm lại tiếp tục hành trình trên con
đường của nhóm chúng. Khi một trong những nhóm này gặp 1 ngã ba khác thì nhóm này lại
có thể tách ra tiếp, và cứ như vậy, các con bị đã hình thành nên 1 quy tắc về việc chia nhóm
như sau: nếu chúng có thể chia thành 2 nhóm mà chênh lệch số bị của 2 nhóm là đúng bằng
K thì tại ngã ba đó chúng sẽ chia làm 2; nếu khơng thì chúng sẽ dừng cuộc hành trình và
đứng ở đó nhấm nháp cỏ non.
u cầu: Cho số lượng bị ban đầu, hãy tính xem cuối cùng có bao nhiêu nhóm bị tất cả. Giả
sử rằng ln có những ngã ba mới trên các con đường.
Input: Từ file văn bản BAI5.INP có cấu trúc:
Gồm một dịng: Chứa 2 số N, K cách nhau ít nhất một dấu cách.
(1≤N≤109, 1≤K≤103)
Output: Ghi vào file văn bản BAI5.OUT có cấu trúc:
Gồm một dòng: Ghi một số nguyên cho biết số lượng nhóm bị có tất cả.
Ví dụ:
BAI5.INP
62
BAI5.OUT
3
Giới hạn:
-40% test: N≤ 102, K≤100.
88
-30% test: N≤ 106 , K≤100.
-30% test: N≤ 109 , K≤1000.
----------------------------------------- HẾT -----------------------------------------
99
ĐỀ KHẢO SÁT ĐỘI TUYỂN HSG 09
Môn thi: Tin học
Thời gian: .... phút (không kể thời gian giao đề) Đề này
có 05 câu, gồm 03 trang.
Tổng quan về các bài thi:
Bài
Tên bài
Bài 1
Trùng nhau
Bài 2
Từ dài nhất
Bài 3
Đếm từ
Bài 4
Đoạn con dài nhất
Bài 5
Số chính phương
Viết chương trình giải các bài toán sau:
Tên file
bai1.*
bai2.*
bai3.*
bai4.*
bai5.*
Dữ liệu vào
bai1.inp
bai2.inp
bai3.inp
bai4.inp
bai5.inp
Dữ liệu ra
bai1.out
bai2.out
bai3.out
bai4.out
bai5.out
Bài 1: (6 điểm) Trùng nhau
Sáng thứ hai tuần này Chí phải đi học sớm để làm trực nhật, sau khi quyét lớp xong Chí
định lau bảng sạch sẽ trước khi các bạn trong lớp đến, nhưng đang định lau thì Chí nhận ra
trên bảng có một bài tốn của các anh chị lớp 12 đang ôn thi đội tuyển, do đang học lập trình
nên Chí rất tị mị bài tốn và muốn thử sức mình. Nhưng loay hoay mãi Chí vẫn chưa biết
giải quyết thế nào nên đành ghi lại bài toán để về hỏi các anh chị đang học đội tuyển lớp 12.
Là thành viên của đội tuyển tin học năm nay, em hãy giúp Chí giải bài tốn này nhé. Nội
dung của bài toán trên bảng như sau:
Cho tệp văn bản bai1.inp gồm:
+ Dòng đầu tiên ghi số n
+ Dòng tiếp theo ghi các số nguyên dương a1, a2, …, a n (với n<=106, ai<=108) Yêu cầu: Ghi
vào tệp bai1.out dãy sau khi đã loại bỏ các phần tử giống nhau. (Các số trong một dãy cách
nhau một dấu cách)
Ví dụ:
bai1.inp
7
23 23 12 1 1 0 9
bai1.out
23 12 1 0 9
Bài 2: (5 điểm) Từ dài nhất
Thấy Chí yêu thích lập trình nên các bạn trong đội tuyển đã gửi cho Chí bài tốn sau:
Người ta định nghĩa: Từ là một nhóm ký tự đúng liền nhau.
Cho một xâu có độ dài khơng q 106 kí tự bao gồm các kí tự lấy từ tập các chữ cái ‘a’
đến ‘z’ và các dấu cách, mỗi từ khơng q 100 kí tự.
Yêu cầu: Đưa ra từ có độ dài dài nhất, nếu có nhiều từ có độ dài bằng nhau thì đưa ra từ đầu
tiên.
Dữ liệu vào: Cho tệp văn bản bai2.inp chứa xâu kí tự như trên.
Dữ liệu ra: Ghi vào tệp văn bản bai2.out chứa từ có độ dài dài nhất cần tìm.
Ví dụ:
học tin
bai2.inp
that la thu vi
10 10
bai2.out
that
•
•
Bài 3 (4 Điểm) Đếm từ
Vì khơng có bố mẹ từ bé nên hằng ngày ngoài thời gian đến trường Chí phải đi chăn
bị th kiếm tiền. Vào một ngày nọ, Chí đã gặp một dịng văn bản hấp dẫn được khắc vào
một tảng đá lớn ở giữa vùng chăn thả bị u thích của mình. Ý nghĩa của dịng văn bản
dường như là từ một ngôn ngữ cổ xưa bí ẩn liên quan đến một bảng chữ cái chỉ gồm ba ký tự
C, O, và W. Mặc dù Chí không thể giải mã văn bản nhưng COW là mẫu từ u thích của Chí,
và cậu tự hỏi có bao nhiêu lần COW xuất hiện trong dịng văn bản.
Chí khơng phiền lịng nếu có những kí tự khác xen kẽ trong COW, miễn rằng các kí tự
xuất hiện theo thứ tự đúng là C, O, W. Chí cũng khơng ngại nếu các lần xuất hiện khác nhau
của COW có chung một số chữ cái. Ví dụ, COW xuất hiện một lần trong CWOW, hai lần
trong CCOW, và tám lần trong CCOOWW.
Em hãy vui lịng giúp Chí đếm xem có bao nhiêu lần COW xuất hiện trong dòng văn
bản đã gặp.
Dữ liệu: Vào từ file văn bản bai3.inp:
Dòng đầu tiên gồm một số nguyên duy nhất N ≤ 105.
Dòng thứ hai chứa một chuỗi gồm N ký tự C, O, hay W.
Kết quả: Ghi ra file văn bản bai3.out chỉ một số nguyên duy nhất là số lần COW xuất hiện
như một dãy con (các kí tự khơng nhất thiết phải liên tục) trong chuỗi input. Ví dụ:
bai3.inp
bai3.out
6
COOWWW
bai4.inp
6
bai4.out
Bài 4. (3 điểm)
7
4
Đoạn con dài
1323312
nhất
Nhiều hơm đi chăn bị Chí được các bạn cho chơi điện tử, lâu dần rồi quen. Ngày nào
không được các bạn cho chơi tí thì Chí cồn cào hết ruột gan vậy. Tối hơm đó biết Bá có nhà
nên Chí đã mị sang nhà để xin Bá cho chơi tí. Biết Bá là người keo kiệt nên kiểu gì cũng bắt
mình làm việc gì đó cho Bá rồi với cho mình chơi. i oăm thay, Bá hơm nay khơng bắt Chí
phải làm việc nhà mà phải thực hiện yêu cầu của mình rồi mới cho chơi điện tử. Chí tức tối
lắm nhưng vì muốn được chơi điện tử nên đành chấp thuận điều kiện của Bá mà cụ thể là giải
1 bài tốn. Chí khơng được đi học mà lại giải một bài tốn khó vậy thì làm sao được, là bạn
của Chí em hãy giúp Chí giải bài tốn nhé. Bài tốn có nội dung như sau:
Cho dãy số nguyên �1, �2, … , ��. Tìm độ dài đoạn con dài nhất gồm các phần tử liên
tiếp của dãy chỉ bao gồm hai giá trị khác nhau. Ví dụ dãy 1, 3, 2, 3, 3, 1, 2 thì đoạn con dài
nhất cần tìm là 3, 2, 3, 3 độ dài 4 gồm hai giá trị là 2 và 3.
Dữ liệu: Vào từ file văn bản bai4.inp:
-
Dòng đầu tiên ghi số nguyên � (1 ≤ � ≤ 106);
Dòng thứ hai ghi � số nguyên �1, �2, … , ��(1 ≤ �� ≤ 109).
Kết quả: Ghi ra file văn bản bai4.out một số nguyên duy nhất là độ dài đoạn con dài nhất chỉ
bao gồm hai giá trị khác nhau theo phương án tìm được.
Ví dụ
11 11
Bài 5. (2 điểm) Số chính phương
Sau một thời gian chơi điện tử, Chí thấy nhàm chán dần mà muốn mình tạo ra được
các trị chơi đó để cho người khác chơi. Sau một thời gian tìm hiểu thì Chí biết cần phải học
lập trình mới tạo ra được các trị chơi đó. Điều đó làm Chí đặt quyết tâm cần phải học lập
trình để thỏa lịng mong ước của mình. Trong q trình học lập trình, Chí rất thích các số
chính phương, muốn tìm hiểu về nó.
Biết rằng số chính phương cũng được biểu diễn bằng tích của một tập các số tự nhiên
phân biệt. Chẳng hạn: 144 = 2 x 3 x 4 x 6; 324=2 x 3 x 6 x 9. Chí hay ngẫm nghĩ về nó mọi
lúc khi có thời gian rãnh. Hơm nay, trong lúc rảnh rỗi, Chí quay sang hỏi Bá và Kiến, với số
tự nhiên N cho trước thì số chính phương lớn nhất được biểu diễn bằng tích của một tập các
số tự nhiên phân biệt từ 1 đến N là bao nhiêu? 2 bạn Bá và Kiến suy nghĩ mãi mà chưa trả lời
được câu đố và quay sang hỏi ngược lại Chí. Vậy Chí đã tìm ra ra số đó bằng cách nào?
Yêu cầu: Cho một số nguyên N, hãy giúp Chí đưa ra số chính phương lớn nhất là tích của
một tập các số tự nhiên phân biệt từ 1 đến N. Số đó có thể rất lớn nên chỉ cần xuất ra phần dư
khi chia số đó cho 1000000007.
Dữ liệu: Từ file văn bản bai5.inp có cấu trúc:
Một dòng duy nhất chứa số nguyên dương N. (N ≤ 4.104)
Kết quả: Ghi vào file văn bản bai5.out có cấu trúc:
Một dịng duy nhất là kết quả bài tốn sau khi đã mod 1000000007
Ví dụ
bai5.inp
bai5.out
7
144
Các số trên một dịng của các file dữ liệu vào được ghi cách nhau bởi ít nhất một dấu cách
---------------- HẾT --------------
12 12
ĐỀ KHẢO SÁT ĐỘI TUYỂN HSG 10
Môn thi: Tin học
Thời gian: .... phút (không kể thời gian giao đề)
Đề này có 05 câu, gồm 02 trang.
Tổng quan bài thi:
Câu
Tên bài
Tên file nguồn
Tên file input
Tên file output
1
Số chính phương
BAI1.*
BAI1.INP
BAI1.OUT
2
Xâu con
BAI2.*
BAI2.INP
BAI2.OUT
3
Xóa số
BAI3.*
BAI3.INP
BAI3.OUT
4
Nấu ăn
BAI4.*
BAI4.INP
BAI4.OUT
5
Tìm số
BAI5.*
BAI5.INP
BAI5.OUT
Dấu (*) trong tên file chương trình biểu thị đuôi file tùy thuộc vào NNLT sử dụng ('pas' đối
với NNLT PASCAL, ‘c’ đối với NNLT C,...).
Hãy lập trình giải các bài tốn sau:
Câu 1. (6 điểm) Số chính phương
Một số chính phương là một số ngun dương có thể biểu diễn dưới dạng bình
phương của một số nguyên dương khác, ví dụ: 1, 4, 9, 25, ... là các số chính phương.
Cho số ngun dương a, hãy tìm số nguyên dương b nhỏ nhất sao cho tích a*b là một
số chính phương.
Dữ liệu vào từ tệp BAI1.INP gồm một dòng chứa số nguyên dương a (1 ≤ a ≤ 109)
Kết quả ghi vào tệp BAI1.OUT số nguyên dương b nhỏ nhất để tích a*b là số chính
phương.
Ví dụ:
BAI1.INP
BAI1.OUT
12
3
Câu 2: (5 điểm) Xâu con
Cho xâu kí tự S chỉ chứa các kí tự chữ cái thường. Hãy tìm độ dài lớn nhất của xâu
con của S mà kí tự đầu tiên và kí tự cuối cùng của xâu con đó là giống nhau.
Dữ liệu vào từ tệp BAI2.INP gồm một dịng chứa xâu S khơng q 10000 kí tự.
Kết quả ghi vào tệp BAI2.OUT độ dài lớn nhất của xâu con tìm được
Ví dụ:
BAI2.INP
BAI2.OUT
abcdag
5
Câu 3: (4 điểm) Xóa số
Cho dãy số nguyên không âm A1; A2; ...; AN. Người ta muốn chọn 2 chỉ số i, j sao
cho 1≤i
nếu tồn tại một chỉ số khác nhau.
Dữ liệu: Vào từ tệp BAI3.INP
6
- Dòng 1 chứ số nguyên dương N (N≤10 )
3
- Dịng 2 chứa N số ngun khơng âm A1 A2…An (Ai≤10 )
Kết quả: Ghi ra tệp BAI3.OUT một số nguyên là số cách chọn 2 chỉ số thoả mãn.
13 13
Ví dụ:
BAI3.INP
BAI3.OUT
5
1 2 3 4 5
Câu 4: (3 điểm) Nấu ăn
6
Có n bạn sinh viên đang tham gia dự thi nấu ăn nhân dịp năm mới và được đánh số
báo danh từ 1 đến n, bạn sinh viên thứ i tham dự với số lượng là ai món ăn. Ban tổ chức sẽ
đánh số các món ăn dự thi như sau: các món ăn của thí sinh thứ nhất đánh số từ 1 đến a1, các
món ăn của thí sinh thứ hai đánh số từ a1+1 đến a1+a2.... và tương tự như vậy cho đến món
cuối cùng. Sau khi chấm thi, Ban tổ chức chọn trao giải cho m món ăn với các số hiệu là p1,
p2, ..., pm. Hãy cho biết các món ăn đạt giải đó thuộc về các bạn sinh viên nào?
Dữ liệu vào từ tệp BAI4.INP gồm 4 dòng:
-
Dòng thứ nhất là số nguyên n (1 ≤ n ≤ 105) là số thí sinh tham gia dự thi.
-
Dòng thứ hai là n số nguyên a1, a2, ..., an (1 ≤ ai ≤ 104) là số lượng món ăn của từng
thí sinh.
-
Dịng thứ ba là số ngun m (1 ≤ m ≤ 104) là số lượng món ăn đạt giải.
-
Dòng thứ tư là m số nguyên p1, p2, ..., pm là số hiệu của m món ăn đạt giải.
Kết quả ghi ra tệp BAI4.OUT m số nguyên s1, s2, ..., sm lần lượt là số báo danh thí sinh
của từng món ăn đạt giải (món ăn pi là của thí sinh số báo danh si).
Ví dụ:
BAI4.INP
BAI4.OUT
5
12 4
54123
3
5 6 12
Câu 5: (2 điểm) Tìm số
Tìm số tự nhiên nhỏ nhất có chữ số hàng đơn vị là D, sao cho khi chuyển chữ số hàng
đơn vị lên vị trí trước chữ số đầu tiên của số đó thì được số mới gấp K lần số cũ.
Ví dụ: D = 7 và K = 5 thì số tự nhiên nhỏ nhất là: 142857 (714285 / 5 = 142857)
Dữ liệu vào từ tệp BAI5.INP gồm 2 số nguyên D và K (0 ≤ D ≤ 9 và 1 ≤ K ≤ 10).
Kết quả ghi ra tệp BAI5.OUT
- Nếu có kết quả, ghi ra số tự nhiên nhỏ nhất có từ 2 chữ số trở lên. Số này khơng có số 0
ở đầu.
- Nếu khơng có kết quả, ghi ra -1.
Ví dụ:
BAI5.INP
7 5
BAI5.OUT
142857
14 14
------------------- Hết -------------------
15 15
