100 đề tin HSG có đáp an

Bài 6/1999 - Giao điểm các đường thẳng
(Dành cho học sinh THPT)
Trên mặt phẳng cho trước n đường thẳng. Hãy tính số giao điểm của các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của bài toán cho trong tệp B6.INP có dạng sau:
- Dòng đầu tiên ghi số n
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.
Bài 7/1999 - Miền mặt phẳng chia bởi các đường thẳng
(Dành cho học sinh THPT)
Xét bài toán tương tự như bài 6/1999 nhưng yêu cầu tính số miền mặt phẳng được chia bởi n đường thẳng này:
Trên mặt phẳng cho trước n đường thẳng. Hãy tính số miền mặt phẳng được chia bởi các đường thẳng này. Yêu cầu tính càng chính xác càng tốt.
Các đường thẳng trên mặt phẳng được cho bởi 3 số thực A, B, C với phương trình Ax + By + C = 0, ở đây các số A, B không đồng thời bằng 0.
Dữ liệu vào của bài toán cho trong tệp B7.INP có dạng sau:
- Dòng đầu tiên ghi số n
- n dòng tiếp theo, mỗi dòng ghi 3 số thực A, B, C cách nhau bởi dấu cách.
Kết quả của bài toán thể hiện trên màn hình.

Bài 10/1999 - Dãy số nguyên
(Dành cho học sinh THCS)
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314..... (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
Em hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương trình để tính toán và so sánh hai kết quả với nhau.
Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên màn hình kết quả là số nằm ở vị trì thứ K trong dãy (1) trên. Yêu cầu chương trình chạy càng nhanh càng tốt.

Bài 11/1999 - Dãy số Fibonaci
(Dành cho học sinh THCS)
Như các bạn đã biết dãy số Fibonaci là dãy 1, 1, 2, 3, 5, 8, .... Dãy này cho bởi công thức đệ qui sau:
F1 = 1, F2 =1, Fn = Fn-1 + Fn-2 với n > 2
1. Chứng minh khẳng định sau:
Mọi số tự nhiên N đều có thể biểu diễn duy nhất dưới dạng tổng của một số số trong dãy số Fibonaci.
N = akFk + ak-1Fk-1 + .... a1F1
Với biểu diễn như trên ta nói N có biểu diễn Fibonaci là akak-1...a2a1.
2. Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.
Input:
Tệp văn bản P11.INP bao gồm nhiều dòng. Mỗi dòng ghi một số tự nhiên.
Output:
Tệp P11.OUT ghi kết quả của chương trình: trên mỗi dòng ghi lại biểu diễn Fibonaci của các số tự nhiên tương ứng trong tệp P11.INP.

Bài 12/1999 - N-mino
(Dành cho học sinh THPT)
N-mino là hình thu được từ N hình vuông 1(1 ghép lại (cạnh kề cạnh). Hai n-mino được gọi là đồng nhất nếu chúng có thể đặt chồng khít lên nhau.
Bạn hãy lập chương trình tính và vẽ ra tất cả các N-mino trên màn hình. Số n nhập từ bàn phím.
Ví dụ: Với N=3 chỉ có hai loại N-mino sau đây:




3-mino thẳng 3-mino hình thước thợ

Chú ý: Gọi Mn là số các n-mino khác nhau thì ta có M1=1, M2=1, M3=2, M4=5, M5=12, M6=35,...
Yêu cầu bài giải đúng và trình bày đẹp.

Bài 13/1999 - Phân hoạch hình chữ nhật
(Dành cho học sinh THPT)
Một hình vuông có thể chia thành nhiều hình chữ nhật có các cạnh song song với cạnh hình vuông (xem Hình vẽ). Xây dựng cấu trúc dữ liệu và lập chương trình mô tả phép chia đó. Tính xem có bao nhiêu cách chia như vậy.
Input
Dữ liệu nhập vào từ tệp P13.INP bao gồm hai số tự nhiên là n, m - kích thước hình chữ nhật.
Output
Dữ liệu ra nằm trong tệp P13.OUT có dạng sau:
- Dòng đầu tiên ghi số K là tổng số