โปรแกรมนับจำนวนการชนของลูกบอลในท่อวงกลม (Python)

โจทย์

มีลูกบอล n ลูกในท่อวงกลมยาว 100 ม. ตำแหน่งเริ่มต้น i เมตรจากจุดเริ่มต้น วิ่ง 0.1 ม./วินาที ทิศทางต่างกัน ชนแล้วเปลี่ยนทิศทาง หาจำนวนครั้งที่ชนใน 10^9+6 วินาที

ตัวอย่าง: [0, 10] → Output: 400000

อัลกอริธึม

1. เรียงตำแหน่ง
2. คำนวณจำนวนรอบ (Lap Count) และจำนวนคู่ที่ชนได้
3. เพิ่มกรณีพิเศษ: ตำแหน่งติดกัน (Diff = 1)

โค้ด Python

def solve(input_array):
    input_array.sort()
    size = len(input_array)
    lap_count = (10**5) * 2
    output = 2 * lap_count * (size // 2) * (size - size // 2)
    stop = 0
    for i in range(size - 1):
        if stop != 1:
            if input_array[i] + 1 == input_array[i+1]:
                output += 2
                stop = 1
            else:
                stop = 0
        else:
            stop = 0
    return output

print(solve([0, 10]))  # Output: 400000

Input / Output

Input:  [0, 10]
Output: 400000