Đề thi chuyên tin

Trường ĐHTH TP Hồ Chí Minh
Hệ PT Chuyên Toán - Tin học
((((( ĐỀ THI CHỌN ĐỘI TUYỂN
Môn: TIN HỌC
(Thời gian làm bài 240 phút)


BÀI 1:
Cho n quả cân có khối lượng đôi một khác nhau: a1 , a2 , .... , an . Người ta lần lượt đặt n quả cân lên một trong hai đĩa cân của một chiếc cân đĩa, mỗi lần đặt một quả cân và đặt lên thì không đặt xuống nữa. Sau khi đặt một quả cân lên người ta ghi lại trạng thái của bàn cân. Nếu lệch về bên trái ghi kết quả là “L”, ngược lại ghi “R” (Cân bằng hoặc lệch về bên phải). Kết quả sau khi đặt hết n quả cân lên là một xâu độ dài n gồm các ký tự “L” hoặc “R”.

Bài toán:
Cho một xâu ký tự độ dài n gồm các ký “L” và “R”. Hãy chỉ ra một thứ tự đặt các quả cân lên bàn cân (chỉ rõ đặt lên bên nào) sao cho kết quả sau khi đặt xong n quả cân là xâu này.
Dữ liệu cho trong File Text có tên nhập từ bàn phím. Dòng đầu là các số ai , các dòng tiếp theo, mỗi dòng ghi một xâu ký tự kết quả.
Kết quả đưa ra File CACHDAT.OUT, trong đó kết quả cho cách đặt một xâu ghi bởi n dòng liên tiếp, dòng thứ i ghi chỉ số của quả cân được đặt lên, sau đó là một trong hai ký tự “L” hoặc “R” chỉ ra tương ứng đặt lên bên trái hay bên phải bàn cân. Hai bộ kết quả khác nhau ghi cách nhau bởi một dòng trống.

BÀI 2:
Một lưới giao thông đường hai chiều giữa n địa điểm được cho bởi ma trận A[i,j] trong đó A[i,j] =1 nếu địa điểm i nối với địa điểm j, còn A[i,j] =0 trong trường hợp ngược lại. Trên mỗi đoạn đường có vạch ở giữa để phân cách. Người ta cần vẽ lại vạch này trên mỗi đoạn đường bằng các xe vẽ vạch, mỗi đoạn một lần. Mỗi một xe khi đã bắt đầu vẽ vạch không nâng được cần lên cho đến khi kết thúc. Mỗi một xe chỉ sử dụng một lần.
Hãy lập trình xác định số lượng ít nhất các xe phải sử dụng để vẽ lại vạch cho tất cả đoạn đường, mỗi xe hãy chỉ ra lộ trình mà nó phải thực hiện.
Dữ liệu cho trong File Text có tên nhập từ bàn phím, trong đó dòng đầu là n, n dòng tiếp theo là chứa bảng A. Kết quả đưa ra màn hình (Quy cách đưa kết quả ra tùy chọn).

BÀI 3:
Có N thợ X1 , X2 ,..., XN và N công việc V1 , V2 ,..., VN. Mỗi một người có thể thực hiện được một số công việc trong N công việc trên.
Lập trình thực hiện các công việc sau:
a) Kiểm tra xem N công việc này có thể bố trí cho N người thợ thực hiện được hay không sao cho mỗi người chỉ thực hiện một công việc và là công việc mà người đó có thể thực hiện được.
b) Biết rằng nếu người thứ i có thể thực hiện được công việc j thì hiệu suất của công việc j mà người i thực hiện là C[i,j]. Hãy chỉ ra một cách bố trí thực hiện các công việc sao cho tổng số hiệu quả thực hiện các công việc là lớn nhất.
Dữ liệu cho trong File Text có cấu trúc như sau:
- Dòng đầu là N.
- Mỗi dòng tiếp theo ghi bộ 3 số i,j và p chỉ ra rằng người thứ i có thể thực hiện được công việc j với hiệu suất công việc là p.
Kết quả đưa ra màn hình (Quy cách tùy chọn).

Ghi chú:
1. Dữ liệu coi như đúng đắn, không phải kiểm tra.
2. Hai số trong File dữ liệu trên cùng một dòng cách nhau bởi dấu cách.
3. Cán bộ coi thi không giải thích gì thêm.



ĐỀ THI HỌC SINH GIỎI PTTH NĂM HỌC 96-97 (Đồng Nai)
MÔN THI: TIN HỌC 12
Ngày thi thứ nhất: 27-12-1996
Thời gian làm bài: 180 phút không kể thời gian giao đề


BÀI SỐ 1:
Có n công việc được đánh số là 1, 2, 3, ...., n (n ( 100). Với mỗi công việc i, ta biết i phải thực hiện sau những công việc k nào đó.
Tại mỗi thời điểm ta chỉ thực hiện một công việc và mỗi công việc chỉ được thực hiện một lần.
Công việc i chỉ được thực hiện nếu biết công việc i không thực hiện sau một công việc nào khác hoặc