ÔN THI 3

Bài 1: Số nguyên tố nhỏ nhất

Cho dãy a gồm n số nguyên. Các số nguyên được đánh số thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình tìm số nguyên tố nhỏ nhất lớn hơn mọi giá trị trong dãy a.

Input: nhập từ file ngtomin.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<=10⁶)

-dòng 2 ghi n số nguyên a_i. Mối số có giá trị tuyệt đối không lớn hơn 10⁷

Output: ghi ra file ngtomin.out gồm 1 dòng

-ghi số nguyên tố cần tìm

Ví dụ:

Input	Output
5 10 7 8 2 13	17

Bài 2: Số chính phương lớn nhất

Cho dãy a gồm n số nguyên. Các số nguyên được đánh số thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình tìm số chính phương lớn nhất trong dãy a.

Input: nhập từ file cphuong.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<=10⁶)

-dòng 2 ghi n số nguyên a_i. Mối số có giá trị tuyệt đối không lớn hơn 10⁷

Output: ghi ra file cphuong.out gồm 1 dòng

-ghi số chính phương  cần tìm

Ví dụ:

Input	Output
8 10 16 8 2 13 -9 4 9	16

Bài 3: Số 2^k

Cho dãy a gồm n số nguyên. Các số nguyên được đánh số thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình tìm những số có dạng 2^k  (k>=0) trong dãy a.

Input: nhập từ file somuk.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<=10⁶)

-dòng 2 ghi n số nguyên a_i. (0<a_i <=10⁷)

Output: ghi ra file somuk.out gồm 1 dòng

-ghi số lượng số có dạng 2^k  trong dãy

Ví dụ:

Input	Output	Giải thích
8 10 16 8 2 13 27 4 9	4	Các số dạng 2k trong dãy: 16, 8, 2,4

Bài 4: Số cuối cùng

Trong lúc rảnh rỗi Bờm đã nghĩ ra một trò chơi như sau:

Từ dãy số a ban đầu. Bờm lấy 2 số ở cạnh nhau cộng lại với nhau để được dãy số mới, sau bước này dãy a giảm đi một số. Bờm lặp lại quá trình này cho đến khi dãy a chỉ còn một số

Hãy viết chương trình in ra số cuối cùng của dãy a theo cách chơi của Bờm.

Input: nhập từ file socuoi.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<=100)

-dòng 2 ghi n số nguyên trong dãy a. Mối số có giá trị tuyệt đối không lớn hơn 100 và cách nhau 1 kí tự trắng.

Output: ghi ra file socuoi.out gồm 1 dòng

-ghi số cuối cùng cần tìm

Ví dụ:

input	output	Giải thích
5 60 3 4 2 6	110	Lần 1: 63 7 6 8 Lần 2: 70 13 14 Lần 3: 83 27 Lần 4:110

Bài 5: Đoạn con có tổng bằng s
Cho dãy a gồm n số nguyên. Các số nguyên được đánh số thứ tự từ 1 đến n. Số thứ i có giá trị là a_i. Hãy viết chương trình tìm kiểm tra trong dãy a có tồn tại đoạn con gồm các phần tử liên tiếp có tổng bằng s hay không?

Input: nhập từ file doancon.inp gồm 2 dòng

-dòng 1: số nguyên n và s (0<n<=10⁶)

-dòng 2 ghi n số nguyên a_i. (0<a_i <=100000)

Output: ghi ra file doancon.out gồm 1 dòng

-ghi số lượng các đoạn con trong dãy có tổng bằng 10

Ví dụ:

Input	Output	Giải thích
8 10 10 16 8 2 13 27 4 9	2	trong dãy có 2 đoạn con có tổng bằng 10 đoạn 1: 10 đoạn 2: 8 2

Bài 6: Chia kẹo

Bờm có n viên kẹo và anh ấy muốn chia chúng thành k phần để tặng cho k em bé. Bờm không thể chia một viên kẹo thành nhiều phần. Số kẹo ở mỗi phần có thể là a hoặc b

Bờm sẽ hài lòng, nếu cả ba điều kiện được đáp ứng cùng một lúc:

* b = a hoặc b = a + 1;

* Số phần có kẹo bằng (a+ 1) phải nhỏ hơn hoặc bằng (k div 2) (chú ý rằng a + 1 không nhất thiết phải bằng b)

* Tổng số kẹo để tặng càng nhiều, càng tốt

Nhiệm vụ của bạn là tìm ra tổng số kẹo đã sử dụng theo cách chia của Bờm

Input: file chiakeo.inp gồm 1 dòng

-chứa 2 số nguyên n và k (0<n,k<=10⁹)

Output: file chiakeo.inp gồm 1 dòng

-in ra tổng số kẹo mà Bờm đã sử dụng để tặng

Ví dụ:

Input	Output	Giải thích
5 2	5	Bờm chia thành 2 phần là 2 viên và 3 viên. Như vậy Bờm dùng hết cả 5 viên kẹo
19 4	18	Bờm chia thành 4 phần là 4, 4, 5, 5. Không thể chia thành 4, 5, 5, 5 vì vi phạm quy tắc thứ 2. Như vậy Bờm dùng hết 18 viên kẹo asdl.

Bài 7: Trộn mảng

Cho hai mảng số nguyên dương A và B lần lượt có N và M số. Các phần tử trong cả hai mảng A và B đều được sắp theo thứ tự tăng dần.

Yêu cầu: hãy tạo mảng C gồm N+M phần tử từ tất cả các phần tử của A và B sao cho các phần tử của C cũng có thứ tự tăng dần.

Input: file tronmang.inp gồm

·       Dòng đầu chứa 2 số N, M (0 < N, M <50 000)

·       N dòng sau, mỗi dòng chứa một số nguyên của mảng A.

·       M dòng tiếp theo chứa 1 số nguyên dương ứng với các phần tử của mảng B.

output: file tronmang.out gồm

 gồm N+M dòng, lần lượt chứa các phần tử của mảng C.

Input	Output
3 2 1 2 5 2 4	1 2 2 4 5

Bài 8: Chia nhóm

Bờm có một dãy n số nguyên a₁, a₂,…, a_n. Bờm cần bạn giúp cậu ấy phân nhóm cho dãy số theo quy tắc sau:

-Các số trong cùng nhóm phải chia hết cho số nhỏ nhất của nhóm

-Số lượng nhóm được chia phải là ít nhất.

-Các số cùng nhóm có thể không ở cạnh nhau.

Input: file chianhom.inp gồm

-Dòng 1: chứa số nguyên n (1≤n≤10²)

-Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (1≤a_i≤10²). Các số cách nhau một kí tự trắng aspo

Output: file chianhom.out gồm một dòng

 -Ghi số lượng nhóm theo quy tắc của Bờm.

Ví dụ:

input	output	Giải thích
3 20 10 30	1	Chia thành 1 nhóm vì tất cả chúng đều chia hết cho 10
5 12 4 15 8 3	2	Nhóm 1: 12, 4, 8 đều chia hết cho 4 Nhóm 2: 15, 3 đều chia hết cho 3
2 9 7	2

Bài 9: Trò chơi chẵn lẻ

Tý và Sửu nghĩ ra trò chơi chẵn lẻ như sau: Cho một dãy số nguyên A có giá trị từ 1 đến n. Hai người chơi thay phiên nhau chọn một số bất kỳ trong dãy A, sau mỗi lượt thì số được chọn bị xóa khỏi dãy. Tý thích chọn những số chẵn, Sửu thì thích chọn những số lẻ.

Nếu đến lượt mình mà người chơi không thể chọn bất kỳ số nào theo ý thích thì người đó sẽ thua. Hãy viết chương trình xác định người chiến thắng. Biết Tý là người chơi lượt đầu tiên.

input: file chanle.inp gồm

Dòng duy nhất chứa một số nguyên n (1  ≤n  ≤10⁹)

output: file chanle.out gồm

Dòng duy nhất in ra tên của người dành chiến thắng

Ví dụ:

Input	output
1	Ty
2	Suu

Bài 10: bán hàng đồng giá

Bờm tham gia bán hàng tại hội chợ kích cầu tiêu dùng huyện Cẩm Mỹ tại công viên văn hóa Sông Ray. Bờm có n mặt hàng. Các mặt hàng được đánh số từ 1 đến n. Mặt hàng thứ i có giá bán là a_i .Để kích thích nhiều người mua hàng của mình, Bờm muốn tất cả các mặt hàng đều có đồng chung một giá.

Bờm không muốn thua lỗ vì vậy Bờm muốn chọn giá theo cách sao cho tổng giá mới không thấp hơn tổng giá ban đầu. Điều đó có nghĩa là nếu Bờm bán tất cả n hàng hóa với giá mới, Bờm sẽ nhận được  tổng số tiền tương đương (hoặc lớn hơn) so với giá ban đầu. Mặt khác, Bờm không muốn khách hàng chê đắt nên trong số tất cả các mức giá có thể chọn, Bờm cần chọn mức giá tối thiểu.

Input: file donggia.inp gồm 2 dòng

-dòng 1: số nguyên n (0<n<10⁷)

-dòng 2: ghi n số nguyên a_i. (0<a_i<=10³). Mỗi số cách nhau 1 khoảng trắng

Output: file donggia.out gồm 1 dòng

-ghi một số nguyên là giá bán mới của n mặt hàng

Input	output
5 1 2 3 4 5	3
3 2 2 2	2