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 ...
