Chương trình Python tìm số lần va chạm bóng trong ống vòng tròn

Giả sử có n bóng trong ống vòng tròn dài 100m. Ban đầu mỗi bóng cách điểm xuất phát i mét. Bóng di chuyển 0.1m/giây theo chiều khác nhau. Khi hai bóng gặp nhau, va chạm và đổi hướng. Nếu quá trình diễn ra 10^9 + 6 giây, tìm số lần va chạm. Khoảng cách ban đầu cho trước.

Ví dụ: input_array = [0, 10], kết quả 400000. Hai bóng, nếu hướng khác nhau thì va chạm 400000 lần.

Giải thuật

1. Sắp xếp input_array
2. size := len(input_array)
3. lap_count := (10^5) * 2
4. output := 2 * lap_count * (size//2) * (size - size//2)
5. stop := 0
6. For i từ 0 đến size-2:
   • Nếu stop != 1:
     • Nếu input_array[i] + 1 == input_array[i+1]: output += 2, stop := 1
     • Ngược lại: stop := 0
   • Ngược lại: stop := 0
7. Trả về output

Ví dụ

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]))

Input

[0, 10]

Output

400000