Giả sử, có n quả bóng trong một ống tròn. Ống dài 100 m và ban đầu, mỗi quả bóng trong ống cách một điểm mà ta gọi là điểm xuất phát là i mét. Bây giờ các quả bóng bắt đầu di chuyển trong ống theo một trật tự tròn theo các hướng khác nhau. Các quả bóng di chuyển 0,1 mét / giây trong ống. Khi hai quả bóng gặp nhau tại một điểm thì xảy ra va chạm và các quả bóng đổi hướng di chuyển. Nếu quá trình này diễn ra trong một thời gian dài, giả sử 10 ^ 9 + 6 giây; chúng ta phải tìm ra số lần các quả bóng tham gia vào một vụ va chạm. Khoảng cách ban đầu của các quả bóng từ điểm xuất phát được đưa ra làm đầu vào.
Vì vậy, nếu đầu vào là input_array =[0, 10], thì đầu ra sẽ là 400000
Có hai quả bóng, và khoảng cách ban đầu của chúng từ vạch xuất phát được cung cấp cho chúng tôi làm đầu vào. Nếu hướng của chúng giống nhau, chúng sẽ không bao giờ xảy ra va chạm. Nhưng, nếu hướng đi của chúng khác nhau, chúng sẽ có lúc va chạm. Một quả bóng sẽ va chạm với một quả bóng khác đúng 400000 lần.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sắp xếp danh sách input_array
- size:=kích thước của input_array
- lap_count:=(10 ^ 5) * 2
- đầu ra:=2 * lap_count * giá trị sàn của (kích thước / 2) * (kích thước - giá trị sàn của (kích thước / 2))
- dừng:=0
- đối với tôi trong phạm vi từ 0 đến kích thước - 1, thực hiện
- nếu điểm dừng không giống 1, thì
- nếu input_array [i] + 1 giống với input_array [i + 1], thì
- đầu ra:=đầu ra + 2
- dừng:=1
- nếu không,
- dừng:=0
- nếu input_array [i] + 1 giống với input_array [i + 1], thì
- nếu không,
- dừng:=0
- trả về kết quả đầu ra
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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]))
Đầu vào
[0, 10]
Đầu ra
400000