Đề thi học sinh giỏi môn Tin học Lớp 12 - Năm học 2014-2015

8. Năm học 2014-2015
8.1. Ngày 1 (26/9/2014)
Câu 1: UCLN
Sơn đi học về khoe với mẹ: “Mẹ ơi hôm nay con đã biết tìm ước số chung lớn nhất (UCLN) của hai số tự nhiên rồi ạ”. 
Mẹ nói: “Thế hả con, thế UCLN lớn nhất của hai số tự nhiên là gì?”. 
Sơn: “UCLN của hai số tự nhiên là số tự nhiên lớn nhất là ước của cả hai số đó mẹ ạ”.
Mẹ hỏi: “Đúng rồi đấy, thế bây giờ mẹ có 5 số tự nhiên con có tìm được UCLN của chúng không?”.
Sơn loay hoay chưa tìm được câu trả lời. 
Yêu cầu: Hãy lập trình giúp Sơn tìm UCLN của 5 số tự nhiên.
Dữ liệu: Vào từ file văn bản CAU1.INP gồm 1 dòng chứa số 5 tự nhiên a, b, c, d, e. Các số cách nhau một dấu cách (1≤ a, b, c, d, e ≤ 109). 
Kết quả: Đưa ra file văn bản CAU1.OUT gồm 1 dòng chứa một số là UCLN của 5 số a, b, c, d, e.
Ví dụ:
CAU1.INP
CAU1.OUT
4 20 8 16 100
4
Câu 2: Đếm số
Sơn là một học sinh đam mê Tin học và rất ngưỡng mộ tác giả người Việt đã viết ra trò chơi FlappyBird nổi tiếng thế giới. Cậu ta muốn tìm hiểu về cách viết trò chơi. Ban đầu, cậu ta muốn viết một trò chơi đơn giản như sau: Mỗi một lần chơi, máy tính sẽ sinh ngẫu nhiên n số nguyên dương ra màn hình, nhiệm vụ người chơi phải đếm được số lượng các số chỉ xuất hiện một lần trong một khoảng thời gian giới hạn. Các mức độ của trò chơi tương ứng với giá trị n lớn hay nhỏ. 
Sơn đã dùng ngôn ngữ lập trình để đếm được một cách nhanh chóng. Em có làm được điều đó không? Hãy vận dụng kiến thức lập trình để đóng vai trò là người chơi nhé.
Yêu cầu: Cho trước n số nguyên dương, đếm số lượng các số chỉ xuất hiện một lần.
Dữ liệu: Vào từ file văn bản CAU2.INP
Dòng 1 chứa số nguyên dương n (1 ≤ n ≤ 106);
n dòng sau, dòng thứ i chứa một số nguyên dương ai (1≤ ai < 106). 
Kết quả: Đưa ra file văn bản CAU2.OUT gồm một số là số lượng các số chỉ xuất hiện một lần.
Ví dụ:
CAU2.INP
CAU2.OUT
5
2 
6 
6 
3 
2
1
Câu 3: Kinh doanh
Cuội sinh ra và lớn lên tại đất nước Anpha, một đất nước chủ yếu sống bằng nghề nông nghiệp. Từ nhỏ Cuội đã có mơ ước xây dựng một nhà máy chế biến nông sản vừa để kinh doanh, vừa để phục vụ cho người dân. Đất nước Anpha có tổng số n ngôi làng, được đánh số từ 1, 2, ..., n. Hai ngôi làng i và j (1≤ i, j ≤ n; i ≠ j) có thể có nhiều con đường đi hai chiều nối với nhau. Với số tiền ban đầu mà Cuội có, Cuội quyết định thực hiện hai việc sau:
Mở một con đường nối trực tiếp giữa hai ngôi làng bất kỳ trong n ngôi làng trên.
Xây dựng một nhà máy chế biến nông sản trên một ngôi làng nào đó trong n ngôi làng trên.
Yêu cầu: Hãy cho biết sản phẩm của nhà máy mà Cuội xây dựng có thể bán nhiều nhất cho bao nhiêu ngôi làng. Biết rằng ngôi làng mà Cuội xây dựng nhà máy và những ngôi làng có đường đi đến ngôi làng mà Cuội xây dựng nhà máy đều có thể mua hàng của Cuội. 
Dữ liệu vào: Từ tệp văn bản CAU3.INP:
Dòng 1 chứa hai số nguyên dương n và m (1 ≤ n ≤ 10000; 0 ≤ m ≤ 10000), n là số ngôi làng của nước Anpha, m là số đường nối trực tiếp giữa hai ngôi làng với nhau;
M dòng sau mỗi dòng chứa hai số nguyên dương i và j (1 ≤ i, j ≤ n, i ≠ j) thể hiện ngôi làng i và j có con đường hai chiều.
Kết quả: Ghi vào tệp CAU3.OUT gồm một số nguyên dương duy nhất là số ngôi làng lớn nhất có thể mua được sản phẩm của Cuội.
Ví dụ:
CAU3.INP
CAU3.OUT
CAU3.INP
CAU3.OUT
10	1
1	2
3
5 2
1 4
2 3
4
8.2. Ngày 2 (27/9/2014)
Câu 4: Cặp số nguyên tố
Cặp số nguyên tố sinh đôi là một cặp gồm hai số nguyên tố liền nhau có dạng (n; n +2), cặp số nguyên tố đầu tiên là (3; 5), sau đó là (5; 7), (11; 13), .... Cứ sau vài năm người ta lại tìm thấy một cặp số nguyên tố sinh đôi lớn hơn. Từ thời Hy Lạp cổ đại Ơclit (Euclide) đã đưa ra giả thuyết: “Có vô số các cặp số nguyên tố sinh đôi”. Đã nhiều thế kỷ trôi qua mà vẫn chưa có ai chứng minh được dự đoán của Ơclit, đến mức người ta coi đó là một điều bí hiểm. Năm 1849 nhà toán học Pháp de Polignac đưa ra giả thuyết tổng quát hơn là: “Với mọi số chẵn k ≥ 2, tồn tại vô hạn các cặp số nguyên tố m, n sao cho m − n = k”. Trong trường hợp k = 2 thì các cặp số (n; m) chính là cặp số nguyên tố sinh đôi.
Yêu cầu: Cho trước số nguyên dương n và một số nguyên dương k < n. Hãy đếm các cặp số nguyên tố nhỏ hơn n sao cho hiệu của chúng bằng k.
Dữ liệu: Vào từ file văn bản CAU4.INP gồm một dòng duy nhất chứa hai số tự nhiên n, k cách nhau bởi một dấu cách (2 ≤ k < N ≤ 106).
Kết quả: Đưa ra file văn bản CAU4.OUT một số duy nhất là số lượng cặp số nguyên tố nhỏ hơn n có hiệu bằng k. Trong trường hợp không có cặp số nào thì in ra số -1.
Ví dụ:
CAU4.INP
CAU4.OUT
CAU4.INP
CAU4.OUT
15 2
3
20 3
1
Câu 5: Mật khẩu
Một xâu ký tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất bằng 6 và xâu chứa ít nhất một chữ cái in hoa (‘A’’Z’), một chữ cái thường (‘a’’z’) và một chữ số (‘0’’9’). 
Ví dụ: ‘A1B2C5’, ‘Tinhoc12’ là hai mật khẩu “an toàn”, còn ‘A3B2’; ‘TinHoc’ đều không phải là mật khẩu “an toàn”. 
Một lần, Sơn nhìn thấy một xâu S có n kí tự. S chỉ gồm các loại ký tự: chữ cái in hoa, chữ cái thường và chữ số. Sơn muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếm xem có bao nhiêu cặp chỉ số (i; j) thỏa mãn điều kiện: 1≤ i ≤ j ≤ n và xâu con gồm các ký tự liên tiếp từ i đến j của S là mật khẩu “an toàn”. 
Yêu cầu: Cho xâu S, tính số lượng cặp chỉ số (i; j) thỏa mãn điều kiện nêu trên. 
Dữ liệu: Vào từ file văn bản CAU5.INP gồm một dòng chứa xâu S có độ dài n kí tự (1 ≤ n ≤ 106). 
Kết quả: Ghi ra file văn bản CAU5.OUT một số là số lượng cặp chỉ số (i; j) tính được. 
Ví dụ:
CAU5.INP
CAU5.OUT
CAU5.INP
CAU5.OUT
abc3456789PQ
6
abc123
0
Câu 6: Lớn nhất
Giáo sư X của quốc gia IT chuyên nghiên cứu về virus máy tính. Để phân tích một mẫu virus lạ giáo sư X chia nhỏ thành n tệp tin (tệp tin thứ i có kích thước là wi) gửi đến máy chủ. Do virus lây lan rất mạnh qua mạng internet, giáo sư X tiến hành copy các tệp tin vào USB rồi copy vào máy chủ. Giáo sư X có Q yêu cầu, mỗi yêu cầu có dạng (u; v): cần tìm kích thước lớn nhất của các tệp tin từ tệp tin thứ u đến tệp tin thứ v. Các bạn hãy giúp giáo sư X thực hiện công việc này! 
Yêu cầu: Tìm kích thước lớn nhất các tệp tin từ tệp tin thứ u đến tệp tin thứ v trong Q yêu cầu của giáo sư X.
Dữ liệu: Vào từ file văn bản CAU6.INP
Dòng 1 chứa 2 số nguyên dương n và Q (1 ≤ n ≤ 50000; 1 ≤ Q ≤ 200000) cách nhau một dấu cách;
Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương wi (1≤ wi < 1000000);
Q dòng tiếp theo mỗi dòng chứa hai số nguyên dương u và v (1 ≤ u ≤ v ≤ n) cách nhau 1 dấu cách là yêu cầu tìm kích thước lớn nhất của tệp tin thứ u đến tệp tin thứ v.
Kết quả: Đưa ra file văn bản CAU6.OUT gồm Q dòng chứa kích thước lớn nhất tìm được tương ứng với yêu của giáo sư X.
Ví dụ:
CAU6.INP
CAU6.OUT
CAU6.INP
CAU6.OUT
5 2
2
3
4
1
4
1 3
4 4
4
1
3 3
1
9
7
1 3
2 3
1 1
9
9
1