Atcoder Regular 110 F - Esoswap

atcoder.jp/contests/arc110/tasks/arc110_f

F - Esoswap

 

구성적 문제인데 감탄스러워서 적어봅니다.

 

문제 해결 방법은 두 가지 관찰이 필요합니다.

 

1. $ N $ 과 $ N - 1 $ 은 서로소이고 서로소이면 어떤 인덱스에 있든 아무 인덱스로 갈 수 있습니다.

2. $ X $ 의 수가 $ X $ 인덱스로 가기 위해선 $ 0 $ 번째 인덱스에 위치해야 갈 수 있습니다.

 

이 두 가지 관찰을 잘 이용해봅시다.

 

그럼 처음 $ N - 1 $ 수를 $ N - 1 $ 에 옮길 수 있습니다.

그리고 $ N - 2 $ 를 계속 움직인다고 가정하겠습니다.

그럼 이 수는 인덱스가 2 씩 증가하도록 오른쪽으로 움직이게 됩니다.

즉 $ N - 1 $ 인덱스를 거치지 않으면 $ N - 2 $ 에 항상 갈 수 있으며

$ N - 1 $ 인덱스를 거친다고 가정했을 때 $ N - 2 $ 가 $ N - 1 $ 이랑 스왑이 되고

$ N - 1 $ 수가 자기자리를 다시 되찾기 위해서 움직이고 움직이다 $ 0 $ 번째 위치에서 $ N - 2 $ 수랑 스왑되게 됩니다.

그럼 $ N - 2 $ 수가 $ 0 $ 번째 인덱스로 가게 되고 여기서 한번 움직이면 $ N - 2 $ 인덱스로 가게 됩니다.

 

$ N - 3 $ 부터 $ 0 $ 까지 동일한 작업을 계속 해주면 됩니다.