원형 튜브에 n개의 공이 있다고 가정합니다. 튜브의 길이는 100미터이고 처음에는 튜브의 각 공이 시작점이라고 하는 지점에서 i미터 떨어져 있습니다. 이제 볼은 다른 방향으로 원형 순서로 튜브 내에서 이동하기 시작합니다. 공은 튜브 내에서 초당 0.1미터를 이동합니다. 두 개의 공이 한 지점에서 만나면 충돌이 발생하고 공의 진행 방향이 바뀝니다. 이 과정이 오래 간다면 10^9 + 6초라고 합시다. 공이 충돌하는 횟수를 알아내야 합니다. 시작점에서 볼의 초기 거리가 입력으로 주어집니다.
따라서 입력이 input_array =[0, 10]과 같으면 출력은 400000
이 됩니다.두 개의 공이 있으며 출발선으로부터의 초기 거리가 입력으로 제공됩니다. 방향이 같으면 충돌하지 않습니다. 하지만 방향이 다르면 시간이 지나면서 충돌하게 됩니다. 한 공이 다른 공과 정확히 400000번 충돌합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 목록 input_array 정렬
- 크기 :=input_array의 크기
- lap_count :=(10^5)*2
- 출력 :=2 * lap_count * (크기 / 2)의 하한값 * (크기 - (크기 / 2)의 하한값)
- 중지:=0
- 0에서 크기 - 1 사이의 i에 대해 수행
- stop이 1과 같지 않으면
- input_array[i] + 1이 input_array[i+1]와 같으면
- 출력 :=출력 + 2
- 중지:=1
- 그렇지 않으면
- 중지:=0
- input_array[i] + 1이 input_array[i+1]와 같으면
- 그렇지 않으면
- 중지:=0
- 반환 출력
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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]))
입력
[0, 10]
출력
400000