Đề 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é.

ThuVienDeThi.com

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:

ThuVienDeThi.com

• 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) …