De thi HSG Tin 12

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