Gcj2010

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

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

Round 3

Problem C. Hot Dog Proliferation

Source: [2]