Đề Thi Tin học không chuyên Trà Vinh 2009

Bài 1 (4 điểm)
Nhập N số nguyên dương (N ≤ 20). Sắp xếp lại dãy bằng cách đưa các số lẻ lên đầu dãy, các số chẵn xuống cuối dãy.
Bài 2 (6 điểm)
Nhập vào thời gian hiện tại là h:m:s – h giờ, m phút, s giây (0 ≤ h < 12, 0 ≤ m,s < 60). Lập trình tìm xem khi nào kim giờ và kim phút gặp nhau?
Có N người xếp hàng mua vé. Ta đánh số họ từ 1 đến N theo thứ tự đứng trong hàng. Thời gian phục vụ bán vé cho người thứ i là ti. Mỗi người cần mua một vé nhưng được quyền mua tối đa 2 vé, vì thế một số người có thể nhờ người đứng ngay trước mình mua hộ. Người thứ i nhận mua hộ vé cho người thứ i+1 thì thời gian mua vé cho 2 người là ri. Tìm phương án sao cho N người đều có vé với thời gian ít nhất.
Dữ liệu vào từ file văn bản TICK.INP
Dòng thứ nhất ghi số nguyên dương N (1Dòng thứ hai ghi N số nguyên dương t1, t2, ..., tn
Dòng thứ ba ghi N-1 số r1, r2, ..., rn-1
Kết quả ghi ra file TICK.OUT
Dòng thứ nhất ghi tổng thời gian phục vụ bán vé
Dòng tiếp theo 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 phải rời khỏi hàng thì qui ước ghi số 0)
Ví dụ
TICK.INP
TICK.OUT

5
2 5 7 8 4
3 9 10 10
17
2 4


Bài 1. Xây tháp
Có N khối đá hình hộp chữ nhật. Người ta muốn xây một cái tháp bằng cách chồng các khối đá này lên nhau. Để đảm bảo an toàn, các khối đá được đặt theo nguyên tắc:
+ Chiều cao của mỗi khối là kích thước nhỏ nhất trong ba kích thước
+ Các mép của các khối đươc đặt song song với nhau sao cho không có phần nào của khối nằm trên bị chìa ra ngoài so với khối nằm dưới.
Hãy tìm phương án xây dựng để tháp đạt được độ cao nhất.
Dữ liệu vào: Cho trong file TOWN.INP:
Dòng đầu tiên là số N
N dòng tiếp, mỗi dòng ghi 3 số nguyên dương là kích thước của một khối đá. Các khối đá đươc đánh số từ 1 theo trình tự xuất hiện trong file.
Kết quả: ghi ra file TOWN.OUT:
Dòng thứ nhất ghi số M là số lượng khối đá dùng để xây tháp
M dòng tiếp theo ghi các khối xếp từ đáy tháp lên đỉnh tháp, mỗi dòng gồm 4 số theo thứ tự K a b c, trong đó K là số hiệu khối đá, a là kích thước chọn làm đáy nhỏ, b là kích thước chọn làm đáy lớn, c là kích thước chọn làm chiều cao.
Các số trên một dòng trong các file được ghi cách nhau ít nhất một dấu cách. Giới hạn số khối đá không quá 5000 và các kích thước của các khối đá không quá 255.
Ví dụ:
TOWN.INP
TOWN.OUT

9
7 5 5
4 4 8
1 1 5
4 2 2
5 1 5
4 2 7
2 9 2
1 3 3
5 5 5
4
1 5 7 5
9 5 5 5
5 5 5 1
4 2 4 2