Kỳ thi chọn học sinh giỏi lớp 12 tỉnh cà mau năm học 2005-2006 môn thi : tin học

	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 2005-2006
ĐỀ CHÍNH THỨC
	- Môn thi	: TIN HỌC (vòng 1)
	- Ngày thi	: 26 – 11 – 2005 
	- Thời gian	: 180 phút (không kể thời gian giao đề)
Bài 1. (4,0 điểm)
Ta biết rằng cách nhân tay 2 số tự nhiên được thể hiện qua ví dụ sau:
x
 212
 346
+
 1272
 848
 636
= 73352
Hãy viết chương trình mô phỏng cách nhân tay 2 số tự nhiên bất kỳ lên màn hình máy vi tính.
Bài 2. (5,0 điểm)
Cho 3 ký tự A, B, C. Từ 3 ký tự trên hãy viết chương trình tạo ra chuỗi ký tự thoả mãn các tính chất sau:
1/ Có độ dài 100;
2/ Không có hai chuỗi con liên tiếp nào giống nhau;
3/ Số ký tự B là ít nhất.
Bài 3. (5,0 điểm)
Cho một bảng A kích thước 40 x 40, trong đó:
A[k,m] = 0 nếu ô [k,m] cho phép “đi qua”
A[k,m] = 1 nếu không cho phép “đi qua” ô [k,m]
Trạng thái ban đầu có một người đứng tại ô [i,j], người này có thể đi mỗi bước sang ô bên cạnh của ô hiện tại, chung cạnh và ô đó là cho phép “đi qua”. Hãy lập trình chỉ cho người đó một lộ trình để thoát ra khỏi bảng. Tức là chỉ ra thứ tự đi từ ô [i,j] tới ô [k,m] trong đó k hoặc m bằng 1 hoặc 40.
Bài 4. (6,0 điểm)
Có N mặt hàng và M nước (N £ 40, M £ 15). 
Cho biết đơn giá mặt hàng i ở nước thứ j là C[i,j] (đơn vị tiền tệ ở nước j). Hàng hoá là không thể phân chia được. C[i,j] nguyên dương. Với số tiền ban đầu là S (đơn vị tiền tệ của nước 1, S £ 200) người ta chỉ có thể mua một loại hàng ở nước 1 và mang sang bán ở nước thứ hai nào đó, dùng tiền thu được mua một loại hàng ở nước này và mang sang bán ở nước thứ ba,  Tiền còn thừa không được phép chuyển đổi. Không được phép mua hàng tại một nước và cũng bán lại hàng này tại nước đó. Hãy lập kế hoạch mua bán hàng hoá sao cho đúng K lần (K £ 10) mua bán hàng ở nước ngoài (một nước có thể được ghé nhiều lần) người ta quay về nước 1, bán tất cả các hàng và thu được nhiều tiền nhất (lần mua hàng đầu tiên tại nước 1 xem như lần mua bán thứ 0, lần bán hàng cuối cùng tại nước 1 xem như lần K + 1).
Dữ liệu: Vào từ file BL4.INP gồm M + 1 dòng.
* Dòng 1: gồm các số M N S K
* Dòng i + 1: gồm N số C[i,1] C[i,2]  C[i,N]
Các số trên một dòng cách nhau ít nhất một dấu cách. 
Kết quả: Xuất ra màn hình dưới dạng:
* Dòng 1: tổng số tiền thu được theo phương án tối ưu.
* K + 2 nhóm dòng tiếp theo (mỗi nhóm gồm 3 dòng):
- Dòng thứ nhất mỗi nhóm ghi số thứ tự của lần mua bán hàng và số thứ tự của nước.
- Dòng thứ hai mỗi nhóm ghi số thứ tự của mặt hàng bán ra, số lượng, đơn giá của mặt hàng này tại nước đó và tổng số tiền thu được khi bán hàng (tính theo đơn vị tiền tệ của nước đó).
- Dòng thứ ba mỗi nhóm ghi số thứ tự của mặt hàng mua vào, số lượng, đơn giá của mặt hàng này tại nước đó và tổng số tiền bỏ ra khi mua hàng (tính theo đơn vị tiền tệ của nước đó).
--- HẾT ---