Đề thi HSG TP. Cần Thơ 2015-2016

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả
1	Số nguyên tố	primemax.*	primemax.inp	primemax.out
2	Rau sạch	vegetables.*	vegetables.inp	vegetables.out
3	Bình chọn giọng hát hay	song.*	song.inp	song.out
4	Xếp hàng mua vé tàu	queue.*	queue.inp	queue.out

Bài 1. Số nguyên tố

Cho số nguyên dương n và dãy gồm n số nguyên với

Yêu cầu:

1. Tìm số nguyên tố lớn nhất trong dãy.

2. Tìm số nguyên nhỏ nhất trong dãy.

Dữ liệu: Vào từ file văn bản primemax.inp

· Dòng đầu tiên chứa số nguyên n

· Dòng thứ hai chứa n số nguyên mỗi số cách nhau bởi một dấu cách.

Kết quả: Ghi ra file văn bản primemax.out

· Dòng thứ nhất ghi số nguyên tố lớn nhất của dãy, nếu không có số nguyên tố thì ghi ra số 0.

· Dòng thứ hai ghi số nguyên nhỏ nhất trong dãy.

Ví dụ:

primemax.inp	primemax.out
15 0 0 1 12 12 -2 -2 -1 -1 -1 -1 4 4 4 4	0 -2
5 11873 5737 9269 7956 432	5737 432

Ràng buộc:

- Có 70% số test ứng với 70% số điểm của bài có

- Có 30% số test ứng với 30% số điểm của bài có

Bài 2. Rau sạch

Một số người nông dân chuyên cung cấp cùng một loại rau sạch cho siêu thị mỗi ngày với một khối lượng nhất định và có giá bán khác nhau. Siêu thị có thể mua một số lượng rau sạch từ những người nông dân này ít hơn hoặc bằng số lượng rau sạch của họ. Vấn đề siêu thị cần quan tâm là tìm cách chọn mua một lượng rau sạch từ những người nông dân với số tiền ít nhất.

Yêu cầu: Cho biết N là khối lượng (kilogram) rau mà siêu thị cần mỗi ngày, M là số người nông dân cung cấp rau cho siêu thị trong đó người nông dân thứ i có giá bán 1 kilogram rau là A_i và có khối lượng (kilogram) rau tối đa có thể bán cho siêu thị là B_i Hãy tính số tiền ít nhất để siêu thị mua được một lượng rau sạch mỗi ngày.

Dữ liệu: Vào từ file văn bản vegetables.inp

• Dòng đầu tiên chứa hai số nguyên N, M
• Dòng thứ i trong M dòng tiếp theo, chứa hai số nguyên A_i và B_i cách nhau một dấu cách

Kết quả: Ghi ra file văn bản vegetables.out chứa một số nguyên là số tiền ít nhất mà siêu thị có thể mua rau sạch mỗi ngày.

Ví dụ:

vegetables.inp	vegetables.out
50 5 5 30 10 40 3 10 8 80 7 30	250

Ràng buộc:

- Có 70% số test ứng với 70% số điểm của bài có

- Có 30% số test ứng với 30% số điểm của bài có

Bài 3. Bình chọn giọng hát hay

Trong vòng chung kết cuộc thi “Bài hát yêu thích” trên VTV3 các thí sinh được đánh số báo danh là một số nguyên dương có giá trị không vượt quá 1500. Khán giả xem truyền hình có thể bình chọn cho thí sinh mình yêu thích bằng cách nhắn tin qua điện thoại di động.

Ban tổ chức nhận được tin nhắn hợp lệ của N khán giả (các khán giả được đánh số từ 1 đến N), khán giả thứ i bình chọn cho thí sinh mang số báo danh a_i .

Yêu cầu: Hãy liệt kê số báo danh của những thí sinh được khán giả bình chọn nhiều nhất theo thứ tự tăng dần.

Dữ liệu: Vào từ file văn bản song.inp

• Dòng đầu tiên chứa số nguyên dương N (N≤10⁶) là số lượng khán giả có tin nhắn bình chọn hợp lệ.
• Dòng thứ i trong N dòng tiếp theo, chứa số nguyên dương a_i là số báo danh của thí sinh mà khán giả thứ i bình chọn.

Kết quả: Ghi ra file văn bản song.out danh sách số báo danh của những thí sinh được khán giả bình chọn nhiều nhất theo thứ tự tăng dần.

Ví dụ:

song.inp	song.out
5 3 1 3 2 2	2 3

Ràng buộc: Có ít nhất 50% số điểm của bài tương ứng với các test có N≤1000.

Bài 4. Xếp hàng mua vé tàu

Có N người xếp hàng mua vé tàu về quê vui tết. Ta đánh số cho những người này từ 1 đến N theo thứ tự mà họ đứng trong hàng. Mỗi người cần mua một vé để về quê vui tết, song người bán vé được phép bán cho mỗi người tối đa hai vé. Vì thế, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết t_i là thời gian cần thiết để người thứ i mua xong vé của mình. Nếu người thứ i+1 rời khỏi hàng và nhờ người thứ i mua hộ vé thì thời gian để người thứ i mua được vé cho cả hai người là r_i.

Yêu cầu: Xác định xem những người nào cần rời khỏi hàng và nhờ người đứng trước mua hộ vé để tổng thời gian phục vụ bán vé là nhỏ nhất.

Dữ liệu: Vào từ file băn bản queue.inp

• Dòng đầu tiên chứa số nguyên dương N
• Dòng thứ 2 chứa N số nguyên dương
• Dòng thứ 3 chứa N-1 số nguyên dương

Kết quả: Ghi ra file văn bản queue.out

• Dòng thứ nhất ghi tổng thời gian phục vụ nhỏ nhất.
• Dòng thứ hai ghi chỉ số của các khách hàng cần rời khỏi hàng (nếu không có ai cần rời khỏi hàng thì quy ước ghi số 0).

Lưu ý: Các số nằm trên cùng một dòng cách nhau 1 dấu cách.

Ví dụ:

queue.inp	queue.out
5 2 5 7 8 4 3 9 10 10	17 2 4