PDA

View Full Version : Bài toán con ếch



Zero
05-09-2002, 12:32
Vào ban đêm các con ếch nhảy lên ruộng lúa làm nát cây lúa tại đó, ếch nhảy theo đường thẳng và mỗi bước nhảy đều cách đều nhau. Một đường ếch là chỗ bị ếch nhảy qua >= 3 bước.

vd : 0 0 0 0 1 0
       0 0 1 0 0 0
       1 0 0 0 0 0

vd : 1 1 1 1 1 1

Vấn đề : cho bản đồ các cây lúa bị dập với kích thước các chiều <= n, tìm đường ếch có nhiều cây lúa bị phá nhất chỉ ra số cây lúa bị phá.
vd
  1 0 0 0 1
  0 0 1 0 0
  1 0 0 0 1
  0 0 0 0 0
>1 1 1 1 1 <

--> đường ếch dài nhất là 5

yêu cầu :
Free Pascal :
n <= 5000 bộ nhớ 64 MB thời gian chạy 2 giây
Turbo Pascal
n<=200 thời gian : 0 giây.

skywalker
06-09-2002, 00:25
anh zero type lại cái đề đi, khó hiểu quá

Zero
06-09-2002, 09:49
Tất cả các chỗ < là nhỏ hơn hoặc bằng.

Bài này là bài thi quốc tế năm nay tại Hàn. Cái đề tôi Type khá kỹ rồi đó nếu bạn cần đề chuẩn vào site của IOI2002 nhé.

huysun
27-09-2008, 14:53
dề bài hay nhỉ, từ năm 2002 đấy.