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

Đề thi học sinh giỏi tin học TP. Cần Thơ 2014-2015

Bài	Tên bài	File chương trình	File dữ liệu vào	File kết quả
1	Tôi là đầu bếp	chief.*	chief.inp	chief.out
2	Thuật toán MDA	mda.*	mda.inp	mda.out
3	Biến đổi gen	dna.*	dna.inp	dna.out
4	Trò chơi lưới mê cung	maze.*	maze.inp	maze.out
5	Xếp hàng	queue.*	queue.inp	queue.out

UVA 10130 - SuperSale (Siêu khuyến mãi)

Link bài gốc
Link chấm bài

Có một chương trình bán hàng siêu khuyến mãi tại siêu thị SuperHyperMarket. Khi mua sắm ở đây, với mỗi mặt hàng, khách hàng có thể chọn mua cho mình với số lượng tối đa là 1 với giá cực kỳ rẻ. Ví dụ, một khách hàng có thể mua sắm: 1 tivi, 1 củ cà rốt. Chúng ta đi cùng một đại gia đình đến siêu thị này để mua sắm. Mỗi thành viên trong gia đình có thể mua sắm nhiều mặt hàng. Chúng ta được cho danh sách các mặt hàng với giá thực thế và khối lượng của nó. Và chúng ta cũng được biết, khối lượng tối đa mà mỗi thành viên trong gia đình có thể mang về. Vấn đề đặt ra là tính giá trị lớn nhất của các mặt hàng mà gia đình chúng ta có thể mua sắm.

Bài toán ba lô có số lượng đồ vật không hạn chế

BÀI TOÁN

Cho n vật có khối lượng lần lượt là a1, a2, …, an và giá trị lần lượt là v1, v2, …, vn, mỗi vật có số lượng không hạn chế.

Cho một ba lô có tải trọng là m

Yêu cầu chọn một số vật để vào ba lô sao cho tổng khối lượng của các vật không vượt quá m và tổng giá trị của các vật là lớn nhất có thể.

Một số bài tập sắp xếp và tìm kiếm

Codeforces 141A - Amusing Joke
Codeforces 160A - Twins
Codeforces 339A - Helpful Maths 
Codeforces 405A - Gravity Flip
Codeforces 490A - Team Olympiad
Codeforces 507A - Amr and Music
Codeforces 37A - Towers
Codeforces 479C - Exams
Codeforces 471B - MUH and Important Things
Codeforces 160B - Unlucky Ticket

Bài toán cái ba lô 0-1 (mỗi đồ vật có số lượng 1)

BÀI TOÁN

Cho n vật có khối lượng lần lượt là a1, a2, …, an và giá trị lần lượt là v1, v2, …, vn

Cho một ba lô có tải trọng là m

Yêu cầu chọn một số vật để vào ba lô sao cho tổng khối lượng của các vật không vượt quá m và tổng giá trị của các vật là lớn nhất có thể.

Bài toán dãy con tăng dài nhất

BÀI TOÁN

Cho một dãy gồm n số nguyên a1, a2, ..., an. Hãy tìm dãy con tăng dài nhất của dãy đã cho.

Dữ liệu:

- Dòng đầu tiên ghi số n

- Dòng thứ hai ghi n số nguyên.

Kết quả:

- Dòng đầu tiên ghi số k cho biết độ dài của dãy con tăng tìm được

- Dòng thứ hai ghi k số cho biết dãy con tăng tìm được