Đề kiểm tra chuyên Tin lần 1, học kỳ 1 năm học 2015-2016

SỞ GIÁO DỤC VÀ ĐÀO TẠO TP. CẦN THƠ TRƯỜNG THPT CHUYÊN LÝ TỰ TRỌNG	ĐỀ KIỂM TRA CHUYÊN LẦN 1 HỌC KỲ I, NĂM HỌC 2015-2016 MÔN: TIN HỌC - KHỐI 11 THỜI GIAN LÀM BÀI: 120 PHÚT
ĐỀ CHÍNH THỨC

TỔNG QUAN ĐỀ KIỂM TRA
(Đề thi gồm 4 bài nằm trên 4 trang)

Bài	Tên bài	File chương trình	File dữ liệu	File kết quả	Điểm
1	Xếp tháp	towers.*	towers.inp	towers.out	3.0
2	Trò chơi 2048	game2048.*	game2048.inp	game2048.out	2.0
3	Biểu diễn đồ thị	graph.*	graph.inp	graph.out	3.0
4	Kế hoạch ôn tập	todolist.*	todolist.inp	todolist.out	2.0
Lưu ý: Phần mở rộng * có thể là pas hoặc cpp (tùy vào ngôn ngữ sử dụng là Pascal hay C++)

UVA 336 - A Node Too Far

ĐỀ BÀI

Để tránh hiện tượng một gói tin bị truyền đi liên tục trong mạng nên mỗi gói tin khi gởi đi sẽ có một thông số thời gian tồn tại (TTL), thông số này cho biết số lượng nút (trạm truyền tin, máy tính,…) có thể truyền lại gói tin này trước khi gói tin bị hủy. Cứ mỗi lần có một nút nhận được gói tin và truyền lại thì TTL của gói tin sẽ bị giảm đi 1. Trong trường hợp gói tin này đến được đích, giá tị TTL sẽ được bỏ qua. Tuy nhiên, nếu gói tin cần phải được truyền đi tiếp mà giá trị TTL bằng 0 thì gói tin sẽ không thể truyền đi tiếp tục.

Bài tập: Cắt thép

Người ta cần cắt một đoạn thép dài l mét tại n vị trí, mỗi vị trí có toạ độ là một số nguyên tính theo khoảng cách bắt đầu từ đầu đoạn thép. Chi phí để cắt là chiều dài của đoạn cần cắt.

Yêu cầu: Hãy tìm chi phí nhỏ nhất để cắt đoạn thép.

Dữ liệu vào: cho trong file văn bản catthep.inp có cấu trúc như sau:

• Dòng đầu ghi 2 số nguyên dương l và n.
• Dòng thứ 2 ghi n số là toạ độ của các vị trí cần cắt, các toạ độ có giá trị lớn hơn 0 và nhỏ hơn l.

Kết quả: ghi ra file văn bản catthep.out chỉ 1 số là kết quả tìm được

Bảng con có tổng lớn nhất

BÀI TOÁN

Cho một bảng hình chữ nhật gồm m dòng và n cột, mỗi phần tử là một số nguyên dương. Hãy tìm một bảng con có tổng các phần tử lớn nhất.
Dữ liệu vào:

• Dòng đầu tiên ghi 2 số nguyên dương m và n
• m dòng tiếp theo, mỗi dòng ghi n số nguyên, mỗi số có trị tuyệt đối không vượt quá 1000

Kết quả: ghi ra 1 số là tổng lớn nhất tìm được
Ví dụ

Input	Output
3 5 -2 6 -1 4 -5 4 2 1 6 3 5 -9 2 1 0	20

Giới hạn:

• 30% số test có m, n ≤ 10
• 30% số test còn lại có m, n ≤ 100
• 40% số test còn lại có m, n ≤ 500

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

UVA 10020

Đề bài: https://uva.onlinejudge.org/external/100/10020.pdf
Ý tưởng:
Sắp xếp lại các đoạn tăng dần theo tọa độ left và đi xét lần lượt các đoạn theo thứ tự này để chọn ra các đoạn phủ tối thiểu theo quy tắc:

• Đầu tiên, gán giá trị phải nhất hiện tại curr = 0.
• Ở mỗi lần chọn ta sẽ chọn 1 đoạn sao cho đoạn này có tọa độ left nhỏ hơn hoặc bằng giá trị phải nhất hiện tại và tọa độ right là lớn nhất có thể, sau khi chọn đoạn này ta cập nhật lại giá trị curr.

Đoạn con có tổng lớn nhất

BÀI TOÁN

Cho một dãy gồm n số nguyên a1, a2, …, an. Hãy tìm một đoạn con (dãy gồm các phần tử liên tiếp nhau) có tổng lớn nhất.

Dữ liệu vào:

• Dòng đầu ghi số n
• Dòng thứ hai ghi n số nguyên a1, a2, …, an, mỗi số có giá trị tuyệt đối không vượt quá 1000.

Kết quả:

Ghi ra 1 số là tổng lớn nhất tìm được.