đề thi HSG tin học lớp 9

Ví Dụ 1: tập hợp hình vuông (hsg 11 08-09)
Gọi S là tập hợp các điểm P(x,y), trong đó x,y là các số nguyên không âm nhỏ hơn hay bằng số nguyên dương N cho trước. Một tập hợp 4 điểm thuộc S là {P1,P2,P3,P4} đuợc gọi là tập hợp hình vuông nếu các điểm P1, P2, P3, P4 là 4 đỉnh của một hình vuông. Hãy đếm số tập hợp hình vuông là tập con của S.
DL vào: THHV.INP
N (<=250)

DL ra: THHV.OUT
M là số tập hợp con của S tìm được.




















Ví Dụ 2: Điểm trên lƯới. (HSG 10 năm 10-11)
Một ngày nọ, Bờm đố Cuội một trò “đơn giản” như sau: Cho một hình vuông có kích thước bất kỳ, ban đầu Bờm có bốn điểm là bốn đỉnh của hình vuông. Ở lần thứ nhất, Bờm thực hiện hai thao tác như sau:
- Thêm một điểm vào mỗi vị trí trung điểm của mỗi cạnh của hình vuông.
- Thêm một điểm vào giao điểm của hai đường chéo của hình vuông.
Sau hai thao tác thực hiện trên, Bờm đã có bốn hình vuông mới. Ở lần thứ hai, Bờm lại thực hiện hai thao tác trên với mỗi hình vuông có được.
Bờm đố Cuội rằng, sau lần thực hiện thứ N, trên hình vuông ban đầu sẽ có tất cả bao nhiêu điểm?
Dữ liệu vào: Một dòng duy nhất chứa số nguyên N (0 ≤ N ≤ 25)
Dữ liệu ra: Một dòng duy nhất ghi số điểm tìm được.
Ví dụ:
Input
Output

Input
Output

Input
Output

1
9

2
25

4
289















Ví Dụ 3: Con thạch sùng (HSG 11 Năm 10-11)
Sau trận mưa tối hôm qua, một bức tường trong nhà có rất nhiều muỗi đậu trên đó. Bức tường có kích thước h x w ô vuông, trong đó h là số hàng được đánh số từ 1 đến h theo chiều từ trên xuống dưới và w là số cột được đánh số từ 1 đến w theo chiều từ trái qua phải. Tại mỗi ô vuông đã có khoảng từ 1 đến 1000 con muỗi đậu ở đó. Một con thạch sùng muốn ăn nhiều nhất muỗi có thể, tùy thuộc vào hạn chế như sau: Nó bắt đầu chọn một ô nhiều muỗi nhất ở hàng trên cùng và ăn số muỗi tại đây. Sau đó chuyển xuống một ô vuông ở hàng bên dưới, tiếp tục ăn muỗi tại đó, con thạch sùng cứ chuyển như vậy đến hết hàng ngang cuối cùng để ăn số muỗi trên mỗi ô. Khi chuyển xuống ô tiếp theo của hàng dưới, nó có thể chuyển theo một trong 3 hướng như hình vẽ.









Yêu cầu: Cho h và w và số muỗi trong mỗi ô, con thạch sùng có thể ăn nhiều nhất là bao nhiêu con muỗi trong một lần duy nhất di chuyển từ hàng trên cùng xuống hàng cuối cùng?
Dữ liệu vào: Dòng đầu ghi hai số nguyên, số đầu tiên là h – số hàng, số nguyên thứ hai là w – số cột. Dòng thứ i trong h dòng tiếp theo ghi w số nguyên m là số muỗi trong mỗi ô. cả các số nguyên đều cách nhau một dấu cách.
Dữ liệu ra: Một dòng duy nhất ghi một số nguyên duy nhất là số muỗi lớn nhất mà con thạch sùng có thể ăn được trong một lần di chuyển duy nhất từ hàng trên cùng xuống hàng dưới cùng.
Ví dụ:
Input
Output

6 5
3 1 7 4 2
2 1 3 1 1
1 2 2 1 8
2 2 1 5 3
2 1 4 4 4
5 7 2 5 1
32

 Hạn chế: 1 ≤ h ≤ 500.
1 ≤ w ≤ 500.
1 ≤ m ≤ 1000.
Giải thích ví dụ: Con thạch sùng chọn như sau: hàng 1 chọn 7, hàng 2 chọn 1, hàng 3 chọn 8, hàng 4 chọn 5, hàng 5 chọn 4, hàng 6 chọn 7. Tổng: 7 + 1 + 8 + 5 + 4 + 7 = 32.