DE THI HSG VONG TINH CA MAU 2007-2008

SỞ GIÁO DỤC VÀ ĐÀO TẠO KỲ THI CHỌN HỌC SINH GIỎI LỚP 12 TỈNH CÀ MAU
CÀ MAU NĂM HỌC 2006-2007

- Môn: Tinhọc
- Ngày thi: 2-12-2007
- Thời gian: 180 phút
Bài1: (4 điểm)
Cho ma trận A kích thước 3x3. hãy điền các số từ 1 đến 9 vào ma trận sao cho trên mỗi hàng đều là một số nguyên tố (tìm mọi trường hợp). Kết quả xuất ra màn hình (không dùng đệ quy).
Bài 2: (5 điểm)
Bạn cần xếp hạng cho học sinh của một lớp. Giả sử mỗi môn học đều là hệ số 1. Bạn hãy chia điểm trung bình cho các học sinh trong lớp và sắp xếp theo thứ tự giảm dần của điểm trung bình. Nếu hai học sinh có cùng điểm trung bình thì sắp họ tên theo thứ tự từ điển ABC.
Dữ liệu: Cho file BL.INP
Dòng đầu ghi số N là số lượng học sinh và số M là số môn học (N<=100 và M<=10)
N dòng tiếp theo, mỗi dòng ghi một chuỗi kí tự là họ và tên học sinh
N dòng tiếp theo, mỗi dòng ghi M số dương là điểm của mỗi học sinh. Mỗi số ghi cách nhau ít nhất một dấu cách.
Họ tên học sinh là các kí tự in hoa.
Kết quả: Xuất ra màn hình danh sách học sinh sau khi xếp hạng.
Bài 3: (5 điểm)
Có N công trường cần vật liệu thi công. Công trường i cung cấp D[i] đơn vị hàng. Hàng được cung cấp từ hai kho A và B. cước vận chuyển một đơn vị hàng từ kho A đến công trường i là A[i]. Cước vận chuyển một đơn vị hàng từ kho B đến công trường i là B[i]. Biết kho A có r đơn vị hàng và tổng số hàng của cả hai kho vừa đủ cung cấp cho N công trường.
Hãy phân phối hàng từ hai kho đến các công trường sao cho tổng cước phí vận chuyển là ít nhất.
Dữ liệu: Cho trong file BL3.INP gồm 4 dòng
Dòng 1: Chứa 2 số N và r
Dòng 2: Chứa N số D[1], D[2],....,D[N].
Dòng 3: Chứa N số A[1], A[2],....,A[N].
Dòng 4: Chứa N số B[1], B[2],.....,B[N].
Dữ liệu là các số nguyên dương (N<=100).
Kết quả: Xuất ra file BL3.OUT gồm 3 dòng
Dòng 1: Ghi một số nguyên dương là tổng chi phí vận chuyển ít nhất
Dòng 2: Ghi N số nguyên dương tương ứng số đơn vị hàng mà khi A cung cấp cho từng công trường theo thứ tự
Dòng 3: Ghi N số nguyên dương tương ứng số đơn vị hàng mà khi B cung cấp cho từng công trường theo thứ tự.
Các số ghi trên cùng dòng ghi cách nhau ít nhất một dấu cách.

Bài 4: (6 điểm)
Một dùng địa hình ABCD hình vuông được chia thành lưới ô vuông NxN. Trên một số ô của lưới có chướng ngại vật. Có tất cả M cần điều khiển vùng địa hình này (M<=15). Với mỗi cần điều khiển Ci (1<=iHãy xác định cần sử dụng những cần điều khiển nào sao cho bạn có thể vượt qua vùng địa hình này với số cần điều khiển cần sử dụng là ít nhất.
Dữ liệu: Vào từ file BL4.INP
Dòng đầu ghi hai số nguyên dương M và N
N dòng tiếp theo mỗi dòng ghi N số biểu diễn vùng địa hình với quy ước ô (i,j)=1 nếu ô đó có chướng ngại vật và bằng 0 nếu không có.
N dòng tiếp theo mỗi dòng ghi N số biểu diễn tác động của các cần điều khiển lên các ô của lưới với quy ước: nếu cần Ck tác động lên ô (i,j) thì bit thứ k của giá trị tại ô này sẽ bằng 1 và bằng 0 nếu ngược lại.

Hết