18788 - Swapity Swap

문제

오역 주의

농부 존의 N (1 <= N <= 100) 마리의 소가 한 줄로 서 있습니다.
왼쪽으로 부터 i 번째 있는 소는 i 라벨을 가지고 있습니다. (1<= i <= N)

농부 존은 소들을 위한 새로운 아침 운동을 떠올렸습니다.
그는 소들에게 다음과 같은 두가지 단계의 과정을 정확히 K 번 반복하라고 말했습니다.
(1<= K <= 10⁹)

1. 왼쪽에서부터 현재 A1... A2 위치에 있는 소들의 순서를 반대로 바꿉니다.
   (1 <= A1 < A2 <=N)
2. 그리고 나서, 현재 왼쪽에서부터 B1... B2 위치에 있는 소들의 순서를 반대로 바꿔줍니다.
   (1 <= B1 < B2 <=N)

이 과정을 정확히 K 번 반복한 후에, 각각의 1<= i <=N 인 i 번째 소의 라벨을 출력해주세요.

입력

첫 줄에 N 과 K 가 먼저 입력됨
둘째 줄은 A1, A2
셋째 줄에 B1, B2

7 2
2 5
3 7

출력

해당 운동 루틴이 끝난 후의, i 번째 소의 라벨을 출력

1
2
4
3
5
7
6

제일 처음 소의 라벨 순서는 1,2,3,4,5,6,7 이다.
운동 루틴의 첫번째 단계를 거치면 1,5,4,3,2,6,7 이 된다.
(2~5번째 소의 순서를 역순으로 바꿨으니까)
두번째 단계를 거치면 1,5,7,6,2,3,4 가 된다.
이걸 2번 반복하면 1,2,4,3,5,7,6 의 순서가 된다.

풀이

각 i번째 소가 x 번 과정을 반복했을 때, 다시 i 위치로 돌아오는 가장 작은 x 를 구한다.
그리고 나서, k 로 x 를 나눈 나머지 값 만큼 돌렸을 때의 라벨을 구하면 된다.

ex) k = 11 이고, 2번 라벨을 가진 소가 운동 과정을 반복했을 때 5번 마다 다시 2번째 자리로 돌아온다고 가정해보자.
11 mod 2 = 1 이고, 결국 1번의 운동 과정을 거친 후에 2번 라벨이 어디로 갔는지 구하면 된다.

역순 으로 바꾼 후의 위치 구하기

1 2 3 4 5 6 7 8 의 순열이 있다고 했을 때, 역순으로 바꾼 후 3 의 위치를 구해보자

3은 1번째 인덱스와 +2 만큼 차이 나므로, 역순시에도 뒤에서 두 번째에 위치하게 된다.

 

 

즉 한번 역순시킨 후 3의 위치는 7 - ( 3 - 1) = (7 + 1) - 3 = 5 로 , 5번째에 위치하게 된다.

 

이를 임의의 숫자영역으로 확대해 보면 다음과 같이

a a+1 a+2 .... b b+1 ..... c 라는 순열이 있고, 역순 후의 b 의 위치를 구해보면

c - (b - a) = c + a - b 번째에 b 가 위치하게 된다.
위의 수식을 이용한 역순 후의 소의 위치를 구하는 함수는 다음과 같다.

int next(int x) { //처음 소의 위치
    if (A1 <= x && x <= A2) x = A1+A2-x; //소가 A1, A2 사이에 위치해 있다면
    if (B1 <= x && x <= B2) x = B1+B2-x; //소가 B1, B2 사이에 위치해 있다면 
    return x; //x 번째 있던 소가 1,2 단계를 거친 후의 위치를 반환한다.
}

코드

#include <iostream>

using namespace std;

int a1,a2;
int b1,b2;

int next(int x) {
    if(x>=a1 && x<=a2) x = a1+a2 - x; 
    if(x>=b1 && x<=b2) x = b1+b2 - x;
    return x;
}

int main() {
    int n,k;
    cin >> n >> k >> a1 >> a2 >> b1 >> b2;
    int res[101];
    for(int i=1; i<=n; i++) {
        int p = 1; //운동 과정 반복한 횟수
        int next_p = next(i); //next position
        while(next_p != i ) {
            p++;
            next_p = next(next_p);
        }
        int modk = k % p;
        for(int j=0; j<modk; j++) {
            next_p = next(next_p);
        }
        res[next_p] = i;
    }
    for(int i=1; i<=n; i++) {
        cout << res[i] << "\n";
    }
}