Gcj2010
รุ่นแก้ไขเมื่อ 02:37, 17 พฤษภาคม 2556 โดย Jittat (คุย | มีส่วนร่วม)
Round 2
C. Bacteria
Source: [1]
แบคทีเรียอยู่บนตารางกริดที่มีขนาดไม่จำกัด แต่ละตัวจะอยู่ในช่องแยกจากกัน
ในแต่ละวินาที การเปลี่ยนแปลงจะเกิดขึ้น (พร้อม ๆ กัน)
- ถ้าแบคทีเรียไม่มีเพื่อนแบคทีเรียที่ติดกันในทิศด้านเหนือและด้านตะวันตกมันจะตาย
- ถ้าช่องที่ไม่มีแบคทีเรียแต่ะมีแบคทีเรียในช่องที่ติดกันในทิศเหนือและทิศตะวันตก จะมีแบคทีเรียใหม่เกิดขึ้นในช่องนั้น
เมื่อพิจารณาตารางกริดแล้ว คุณพบว่ามีแบคทีเรียอยู่เป็นจำนวนบวกที่มีค่าจำกัดในบางช่องของพื้นที่
ให้คำนวณว่าจะใช้เวลาเท่าใด ก่อนที่แบคทีเรียจะตายหมด
ด้านล่างเป็นตัวอย่างของตารางกริดที่เริ่มด้วยแบคทีเรียจำนวน 6 ตัว ในรูปดังกล่าวจะใช้เวลา 6 วินาที ก่อนที่แบคทีเรียจะตายหมด ช่องที่มี 1 แทนช่องที่มีแบคทีเรีย ช่องที่เป็น 0 แทนช่องที่ไม่มีแบคทีเรีย
000010 011100 010000 010000 000000 000000 001110 011000 010000 000000 000000 000110 001100 011000 000000 000000 000010 000110 001100 000000 000000 000000 000010 000110 000000 000000 000000 000000 000010 000000
000000 000000 000000 000000 000000
