APMO 2005 #4
ในเมืองเล็กๆแห่งหนึ่ง มีบ้าน n*n หลัง ซึ่งกำหนดโดยดัชนี (i,j);1ฃi,jฃn โดยที่ (1,1) แทนบ้านมุมซ้ายบน i,j เป็นแถงและหลัก ตามลำดับ เมื่อเวลา 0 ไฟไหม้บ้าน(1,c); 1ฃcฃn/2 และในทุกๆช่วงเวลา[t,t+1] นักดับเพลิงป้องกันบ้านที่ยังไม่ถูกไฟไหม้ได้เพียงหลังเดียวเท่านั้น และในขณะเดียวกันนี้ ไฟก็ลามไปยัง"เพื่อนบ้าน" ทั้งหมดที่ยังไม่ได้รับการป้องกัน บ้านที่ได้รับการป้องกันแล้วจะถือว่าได้รับการป้องกันตลอดไป กระบวนการนี้จบลงเมื่อ ไฟ่ไม่สามารถลามต่อไปได้อีก นักดับเพลิงสามารถป้องกันบ้านจากไฟไหม้ครั้งนี้ได้มากที่สุดกี่หลัง
บ้าน(i,j) เป็น"เพื่อนบ้าน"ของ (k,l) ถ้า abs(i-k)+abs(j-l)=1
__________________
For the things of this world cannot be known without a knowledge of mathematics.
|
09 พฤษภาคม 2005, 22:12
หัวข้อคล้ายคลึงกัน
