HSG Tin học tỉnh Bình Phước 2011

ĐỀ THI HỌC SINH GIỎI CẤP TỈNH NĂM 2010 - 2011
MÔN: TIN HỌC
Thời gian: 180 phút.
Bài 1. (7 điểm):
Có N người ngồi xung quanh một bàn tròn. Cho phép đổi vị trí của hai người bất kỳ ngồi cạnh nhau, sao cho khi kết thúc việc đổi chỗ, vị trí của hai người bất kỳ ngồi cạnh nhau trước đây cũng sẽ được “đổi chỗ”, tức là nếu như ban đầu A ngồi bên trái B, thì sau khi đổi chỗ A ngồi bên phải của B. Hỏi có bao nhiêu cách biến đổi như vậy và hãy chỉ ra ít nhất một cách nào đó.
Dữ liệu vào Nhập N từ bàn phím;
Dữ liệu ra được lưu vào file BAI1.OUT (dòng đầu tiên là kết quả có bao nhiêu cách đổi chỗ, các dòng tiếp theo là các vị trí đổi chỗ cho nhau).
Ví dụ: Nhập N=3
BAI1.OUT như sau:
1
23
(Đề trên chép lại nguyên văn đề sở, ngay cả file Out, 23 (không có dấu cách))
Bài 2.(7 đ) Đoạn thẳng và hình chữ nhật
Trong hệ tọa độ Đề Các vuông góc (xOy) có hình chữ nhật và một đoạn thẳng như hình vẽ. Đoạn thẳng được xác định bởi tọa độ của điểm đầu và tọa độ của điểm cuối, hình chữ nhật được xác định bởi tọa độ đỉnh trái trên và đỉnh phải dưới. Ví dụ như hình vẽ đoạn thẳng được xác định bởi tọa độ (4,9) và (11,2), hình chữ nhật được gọi là cắt nhau nếu giữa đoạn thẳng và hình chữ nhật có ít nhất một điểm chung.
Như vậy cứ cho một bộ số gồm 8 chữ số ta sẽ có một đoạn thẳng và một hình chữ nhật được xác định như trên. Hãy lập chương trình khi nhập vào một bộ số gồm 8 chữ số từ bàn phím thì cho kết quả là đoạn thẳng và hình chữ nhật được xác định bởi bộ số đó có cắt nhau hay không?
Bài 3. (6 đ). Đường đi của robot.
Cho một bảng ô vuông (n*n) ô (2<=n<=100) các ô ghi các số là 0 hoặc 1. Tìm đường đi của Robot, từ góc trái trên xuống góc phải dưới theo nguyên tắc chỉ được dịch chuyển sang phải và xuống dưới sao cho các số trên đường đi tạo thành một số nhị phân có giá trị lớn nhất.
Dữ liệu vào: Ghi trong tập tin văn bản ROBOT.INP gồm:
Dòng đầu tiên ghi giá trị n.
N dòng tiếp theo, trên mỗi dòng ghi n số 0 hoặc 1 các số này cách nhau ít nhất một khoảng trắng.
Dữ liệu ra: Ghi vào tập tin văn bản ROBOT.OUT gồm một số duy nhất là giá trị thập phân của chữ số nhị phân được tạo thành ở trên.
Ví dụ:
ROBOT.INP
ROBOT.OUT

5
1 0 1 1 0 0 0 1 0 1 0 0 1 0 1 1 0 0 1 1 1 1 0 1 0
374


** HẾT!**