파이썬에서 마지막 풍선을 받은 아이의 시작 인덱스를 찾는 프로그램은?

<시간/>

n명의 아이들이 원 안에 서서 풍선을 받기 위해 기다리고 있다고 가정해 봅시다. 분배는 k번째 자식(첫 번째 인덱스 0)부터 시작하여 원을 떠난 풍선을 제공합니다. 이제 모든 k 번째 자식은 풍선을 받는 자식이 하나만 남을 때까지 시계 방향으로 풍선을 얻습니다. 따라서 n과 k가 있는 경우 마지막 풍선을 받는 자식의 시작 인덱스를 찾아야 합니다.

따라서 입력이 n =3 k =2와 같으면 출력은 1이 되고 첫 번째 라운드에서 자식 2는 풍선을 받고 원이 [0, 1]이 되도록 둡니다. 두 번째 라운드에서는 어린이 0이 풍선을 받고 원이 [1]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

arr :=범위 0에서 n까지의 새 목록
초기화 :=0
arr의 크기가 1보다 큰 동안 수행
- remove :=(init + k) arr의 모드 크기
- 삭제 arr[제거]
- 초기화 :=제거
반환 arr[0]

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

class Solution:
   def solve(self, n, k):
      arr = list(range(0, n))
      init = 0
      while len(arr) > 1:
         remove = (init + k) % len(arr)
         del arr[remove]
         init = remove
      return arr[0]

ob = Solution()
n = 3
k = 2
print(ob.solve(n, k))

입력

3,2