Gcj2010

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

C. Hot Dog Proliferation

Source: [2]

ร้านขาย hot dog หลายร้านได้เปิดกิจการขึ้นที่แยกบนถนนที่มีทิศตะวันออก-ตะวันตกสายหนึ่งที่ยาวมาก ปัญหาก็คือ ร้านขาย hot dog หลายร้านอาจจะขายอยู่ที่แยกเดียวกัน ทำให้แย่งลูกค้ากัน

คนขาย hot dog เลยมีแผนการดังนี้:

ถ้ามีคนขายตั้งแต่สองคนขึ้นไปที่แยกใด ๆ คนขายสองคนพอดีจะย้ายที่ กล่าวคือ

• จะมีคนขายคนหนึ่งย้ายไปขายที่แยกถัดไปทางทิศตะวันออกของแยกเดิม
• คนขายอีกคนจะย้ายไปขายที่แยกในทิศตะวันตกของแยกเดิม

เนื่องจากถนนยาวมาก จึงไม่ต้องกังวลว่าแยกจะไม่พอ ให้ตำแหน่งเริ่มต้นของคนขาย hot dog ทั้งหมด ให้คุณคำนวณจำนวนครั้งของการย้ายตามวิธีด้านบนที่น้อยที่สุด ที่จะทำให้ไม่มีคนขายสองคนขายอยู่ที่แยกเดียวกัน

พิจารณาตัวอย่างด้านล่าง สมมติว่าถนนมีจำนวนคนขาย hot dog ดังนี้ (จากทิศตะวันตกไปตะวันออก):

... 0 0 2 1 2 0 0 ...

เหล่าคนขายจะสามารถกระจายตัวออกไปได้ โดยการย้าย 3 ครั้ง ดังนี้:

... 0 0 2 1 2 0 0 ...
        |
        +--- ย้ายตรงนี้

... 0 1 0 2 2 0 0 ...
          |
          +--- ย้ายตรงนี้ 

... 0 1 1 0 3 0 0 ...
            |
            +--- ย้ายตรงนี้

... 0 1 1 1 1 1 0 ...