Baltic2013

Ball Machine

เรามีเครื่องจักรลูกบอล (ball machine) ที่สามารถพิจารณาว่าเป็น rooted tree ได้ โหนดใน tree ดังกล่าวจะมีหมายเลขตั้งแต่ 1 ถึง N แต่ละโหนดอาจจะว่างหรือมีลูกบอลหนึ่งลูก เมื่อเริ่มต้น ทุกโหนดอยู่ในสถานะว่าง ขณะที่ทำงาน เครื่องจักรจะสามารถทำงานได้สองแบบ:

1. เพิ่มลูกบอล k ลูกเข้าใน ball machine: ลูกบอลจะถูกใส่ทีละลูกที่โหนด root ถ้าลูกบอลมีโหนดที่ว่างที่ติดกันด้านล่าง ลูกบอลจะไหลลงไปที่โหนดนั้น ถ้ามีโหนดลูกที่ว่างหลายโหนด ลูกบอลจะเลือกโหนดที่มีโหนดหมายเลขน้อยที่สุดในต้นไม้ย่อยที่มีโหนดนั้นเป็น root

ถ้าลูกบอลไหลลงไปหลาย ๆ ระดับ ลูกบอลจะเลือกโหนดลูกตามเงื่อนไขดังกล่าวในทุก ๆ ระดับ

ตัวอย่างเช่น ถ้าเราใส่ลูกบอลสองลูกลงในเครื่องจักรในรูปด้านล่าง ลูกบอลทั้งสองจะไหลไปที่โหนด 1 และ 3 ลูกบอลลูกแรกจะไหลจากโหนด 4 ไปยังโหนด 3 เนื่องจากโหนด 3 นั้นว่างอยู่และมีโหนด 1 อยู่ในต้นไม้ย่อยของมัน (ที่ประกอบด้วยโหนด 3 และ 1) จากนั้นลูกบอลจะไหลจากโหนด 3 ไปยังโหนด 1 ลูกบอลลูกที่สองจะไหลจากโหนด 4 ไปยังโหนด 3 และหยุดที่ตำแหน่งนั้น