PRE THI HUYỆN #11 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Trò chơi - Qb 2018-2019	50 (p)	1.0s	30M
2	Nuôi bò	50 (p)	1.0s	1G
3	Tổng nguyên tố	50 (p)	1.0s	1G
4	Bộ tộc(HSG9 2017-2018)	50 (p)	1.0s	1G

1. Trò chơi - Qb 2018-2019

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 30M Input: game.inp Output: game.out

Trong hội chợ xuân 2019, Ban tổ chức đã đưa ra rất nhiều trò chơi hấp dẫn và đặc sắc. Để các trò chơi thêm phần thú vị, Ban tổ chức đưa ra quy định như sau: Mỗi người tham gia sẽ bắt ngẫu nhiên một số nguyên dương và chỉ được chơi những trò chơi có số thứ tự là ước của số nguyên đã bắt được. Tuy nhiên, trò chơi số \(1\) và \(2\) bị hỏng nên không có ai chơi được. Sau khi kết thúc hội chợ, Ban tổ chức muốn thống kê xem trò chơi nào có đông người chơi nhất và số lượng là bao nhiêu. Là một lập trình viên siêu việt, bạn hãy giúp Ban tổ chức làm việc này.

Yêu cầu:

Cho số nguyên n là số lượng người tham gia và dãy gồm \(n\) số nguyên dương là các số ngẫu nhiên mà mỗi người tham gia bắt được. Hãy đưa ra số lượng người chơi tối đa có thể của một trò chơi.

Dữ liệu vào:

Được cho ở tệp văn bản GAME.INP có cấu trúc như sau:

Dòng 1: Ghi một số nguyên \(n\) là số lượng người tham gia (\(1 \leq n \leq 10^4\)).
Dòng 2: Ghi \(n\) số nguyên \(A_i\) là các số mà mỗi người tham gia bắt được (\(1 \leq A_i \leq 10^5\)).

Dữ liệu ra:

Ghi ra tệp văn bản GAME.OUT có cấu trúc như sau:

Dòng 1: Ghi một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Input

5
6 9 5 9 7

Output

Ví dụ:

Input

5
3 5 7 11 15

Output

2. Nuôi bò

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: cow.inp Output: cow.out

Vào mùa xuân năm nay, bác Tom quyết định đầu tư lớn để chăn nuôi bò. Bác đã xây dựng \(n\) chuồng và đánh số thứ tự các chuồng từ \(1\) đến \(n\). Mỗi chuồng bác chỉ nhốt duy nhất một con bò và các con bò này không được phép di chuyển qua chuồng khác. Ngoài \(m\) con bò bình thường đã có, bác quyết định đầu tư nuôi thêm một số con bò Châu Phi nữa. Tuy nhiên, những con bò Châu Phi này lại rất khó tính, chúng chỉ thích ở những chuồng được đánh số chẵn và nhất quyết không ở những chuồng đánh số lẻ. Vì vậy, bác Tom đã tìm đến bạn nhờ đếm xem các chuồng của nhà bác có thể nhốt được thêm tối đa bao nhiêu con bò Châu Phi này.

Yêu cầu

Tìm số lượng bò Châu Phi có thể nhốt thêm.

Dữ liệu vào

Được cho ở tệp COW.INP có cấu trúc như sau

Dòng 1: Ghi 2 số nguyên \(n\) và \(m\) cách nhau bởi một kí tự trắng (\(1 ≤ m ≤ n ≤ 10^6\)).
Dòng 2: Ghi \(m\) số nguyên đôi một khác nhau, các số cách nhau bởi 1 kí tự trắng thể hiện số thứ tự của các chuồng đã được nhốt bò.

Dữ liệu ra

Ghi ra tệp văn bản COW.OUT có cấu trúc như sau
- Dòng 1: Ghi một số nguyên duy nhất là kết quả tìm được.

Ví dụ 1

Input

6 3
3 5 2

Output

Ví dụ 2

Input

10 5
1 7 3 6 9

Output

3. Tổng nguyên tố

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: sprime.inp Output: sprime.out

Một số tự nhiên \(n\) có thể phân tích được dưới dạng tổng của hai số nguyên tố.
Ví dụ: Số \(8\) có một cách phân tích thành tổng hai số nguyên tố là \(3\) và \(5\); Số \(11\) không có cách phân tích nào thành tổng của hai số nguyên tố.

Yêu cầu

Cho số nguyên dương \(n\), hãy đếm số cách phân tích \(n\) thành tổng của hai số nguyên tố.

Dữ liệu vào

Cho trong file văn bản SPRIME.INP có cấu trúc như sau:

Dòng \(1\): Ghi số nguyên dương \(n\) ( \(1≤ n ≤ 10^6\)).

Dữ liệu ra

Ghi ra file văn bản SPRIME.OUT theo cấu trúc như sau:
- Dòng \(1\): Ghi số nguyên đếm được.

Ví dụ 1

Input

Output

Giải thích

Trong ví dụ trên số 30 có 3 cách phân tích thành tổng của hai số nguyên tố như sau: 30 = 7 + 23; 30 = 11 + 19 và 30 = 13 + 17.

4. Bộ tộc(HSG9 2017-2018)

Điểm: 50 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: clan.inp Output: clan.out

Trên một hòn đảo xinh đẹp, có \(n\) người thuộc nhiều bộ tộc sinh sống. Người dân ở đây rất hiền hòa, mỗi người thuộc một bộ tộc nào đó. Một nhà nhân chủng học muốn biết trên đảo có bao nhiêu bộ tộc. Ông nghĩ ra một cách, ông gặp và hỏi từng người trong \(n\) người trên đảo với một câu hỏi: “Bộ tộc của bạn có bao nhiêu người?”. Ông nhận được câu trả lời từ họ đó là số lượng người trong bộ tộc của họ. Từ kết quả thu được, nhà nhân chủng học sẽ xác định được số lượng bộ tộc khác nhau trên đảo.

Yêu cầu:

Với \(n\) câu trả lời của \(n\) người dân, hãy xác định số lượng bộ tộc có trên đảo.

Dữ liệu vào:

Cho trong file văn bản CLAN.INP, có cấu trúc như sau:

Dòng 1: Ghi số nguyên dương \(n\) (\(1 ≤ n ≤ 100000\)).
Dòng 2: Ghi \(n\) số nguyên dương \(a_i\), là \(n\) câu trả lời nhận được. Các số được ghi cách nhau ít nhất một dấu cách (\(1 ≤ a_i ≤ n\)).
Dữ liệu vào luôn đảm bảo để bài toán có nghiệm.

Dữ liệu ra:

Ghi ra file văn bản CLAN.OUT, theo cấu trúc như sau:

Dòng 1: Ghi một số nguyên dương, là số lượng bộ tộc trên đảo tìm được.

Ví dụ 1:

Input

10
5 1 2 5 5 2 5 5 2 2

Output

Giải thích:

Trong ví dụ trên có 4 bộ tộc gồm một bộ tộc 5 người (có cùng câu trả lời là 5); hai bộ tộc mỗi bộ tộc 2 người và một bộ tộc chỉ có 1 người (có câu trả lời là 1).