Bài tập BD HSG Tin

Bài 1: Dãy nhị phân
Cho tập S tất cả các dãy nhị phân có độ dài N. Trong đó mỗi dãy không có hai bit 1 nào kề nhau. Các dãy này được xếp theo chiều tăng dần của số nguyên tương ứng mà dãy biểu diễn. theo thứ tự đó, mỗi dãy có một số hiệu, bắt đầu từ 1. Ví dụ với n = 5
Số hiệu Dãy
00000
00001
00010
00100
00101
……. …….
Dữ liệu vào:
Cho ở file NHIPHAN.INP gồm một số dòng, mỗi dòng có một trong hai loại:
- Loại 1 ghi ba số 1, n và m, trong đó n là độ dài dãy, m là số hiệu của dãy nhị phân cần tìm, 2<=n <=200.
- Loại 2 ghi số 2 và một xâu nhị phân.
Các khoản liên tiếp trên một dòng và cách nhau một dấu cách.
Dữ liệu ra: File NHIPHAN.OUT. Với mỗi dòng của file vào ghi ra dòng tương ứng của file ra như sau: với dòng loại 1, ghi ra dòng tương ứng dãy nhị phân độ dài n có số hiệu m; với dòng loại 2, ghi ra dòng tương ứng số hiệu m của dãy nhị phân.
Ví dụ:
NHIPHAN.INP
NHIIPHAN.OUT

1 5 5
2 00101
00101
5

Bài 2; Food
Trên một sân hình chữ nhật mxn ( 1<=m, n <= 100) được chia thành các ô vuông đơn vị. các dòng được đánh số từ 1 đến m, các cột được đánh số từ 1 đến n, mỗi ô nằm trên giao của dòng i và cột j được gọi là ô (i, j) có chứa một lượng thức ăn là 1 số nguyên a[i, j]. Một con kiến xuất phát từ ô (1, 1) muốn đi qua sân để đến dòng thứ m. Con kiến chir có thể đi theo một dòng chia nhỏ trên sân ứng với một dòng của bảng chữ nhật hoặc đi theo trên một cột của sân, trên đường đi nó lấy hết thức ăn ở ô mà nó đi qua. Hãy chỉ ra đường đi giúp con kiến có được nhiều thức ăn nhất.
Dữ liệu vào: file Food.inp như sau:
- Dòng 1: 2 số m, n
- Trong m dòng tiếp theo ghi n số nguyên là lượng thức ăn trong bảng hình chữ nhật m xn.
Dữ liệu ra: cho trong file Food.out như sau:
- Dòng đầu tiên chứa lượng thức ăn nhiều nhất mà con kiến đã tìmdduwowcjDdd.
- Dòng tiếp theo ghi các toạ độ của đường đi con kiến từ ô (1, 1) đến ô nằm trên dòng m mà lượng thức ăn nhiều nhất ở dòng trên.
FOOD.INP
FOOD.OUT

3 5
7 3 8 1 5
8 8 3 14 1
6 15 19 1 1
45
(1, 1)( (2,1) ( (2, 2) ( (2, 3) ( (3,3)


Truyền tin trên mạng
Có một nhóm n học sinh đánh số từ 1 đến n, một số người trong họ có thể liên lạc được với nhau qua E-mail ( 1 chiều). Khi biết một thông tin mới họ dùng E-mail gửi thông tin đó cho nhau. Thầy giáo chủ nhiệm biết E-mail của mọi bạn, và có một thông tin đặc biệt muốn gửi cho tất cả n học sinh này. Hãy tìm số ít nhất học sinh mà thầy giáo sẽ gửi E-mail cho họ để học truyền tin cho mọi người còn lại.
Dữ liệu vào cho ở file văn bản THTIN.INP:
- dòng đầu số n ( <=1000).
- n dòng tiếp theo, dòng thứ i trong n dòng chứa danh sách các HS mà HS thứ i có thể gửi E-mail cho họ. Nếu danh sách rỗng thì dòng này bỏ trống.
Kết quả ghi ở file THTIN.OUT:
- dòng đầu ghi số k là số người ít nhất nhận thông tin trực tiếp từ thầy giáo.
- Dòng thứ 2 ghi số hiệu k người
Ví dụ
THTIN.INP
THTIN.OUT

6
2 3
1
1
5
4
3
1
4
6

Quản lý công trình
Có n công trình cần phải thực hiện. Để thực hiện công trình thư si thì cần có ki công cụ trong p công cụ ( ki <= p). Một công trình chỉ được thực hiện khi có đầy đủ công cụ, hai công trình không thể đồng thời sử dụng chung một công cụ.
Giả sử rằng mỗi công trình với đầy đủ các công cụ có thể thực hiện mất cùng một khoảng thời gian.
Hãy xác điịnh khoảng thời gian ngắn nhất để thực hiện xong tất cả n công trình.
Dữ liẹu vào từ file CT.INP gồm:
- Dòng đầu chứa 3