Code Jam to I/O 2016 for Women - B. Dance Around The Clock

Problem

The owner of a prestigious ballroom has painted a beautiful circular clock on the dance floor, and a group of D dancers numbered 1 through D are about to literally "dance around the clock". They are standing in a circle, with dancer 1 at the 12:00 position of the circle and the other dancers going clockwise around the circle in increasing numerical order. The number of dancers is even.

The dance will go on for N turns. On the i-th turn (counting starting from 1), the following will happen:

• If i is odd, then the dancer currently at the 12:00 position will swap positions with the next dancer in clockwise order. Then, going past those two, the next pair of dancers in clockwise order will swap positions, and so on, all the way around the ring clockwise, until all dancers have participated in exactly one swap.
• If i is even, then the dancer currently at the 12:00 position will swap positions with the next dancer in counterclockwise order. Then, going past those two, the next pair of dancers in counterclockwise order will swap positions, and so on, all the way around the ring counterclockwise, until all dancers have participated in a swap.

For example, this diagram shows the initial state and two turns of a dance with eight people.

Which two dancers will be next to dancer number K when the dance is over?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with three integers D, K, and N: the total number of dancers, the number of one of the dancers, and the number of turns the dance will go on for.

Output

For each test case, output one line containing Case #x: y z, where:

• x is the test case number (starting from 1).
• y is the number of the dancer who will be standing to dancer number K's left (that is, one step away in clockwise order) when the dance is over.
• z is the number of the dancer who will be standing to dancer number K's right (that is, one step away in counterclockwise order) when the dance is over.

Limits

1 ≤ T ≤ 100.
D is even.
1 ≤ K ≤ D.

Small dataset

4 ≤ D ≤ 10.
1 ≤ N ≤ 10.

Large dataset

4 ≤ D ≤ 10⁸.
1 ≤ N ≤ 10⁸.

Sample

Input	Output
3 8 3 1 8 4 2 4 1 8	Case #1: 6 4 Case #2: 1 7 Case #3: 2 4

풀이

문제를 요약하자면

짝수명의 댄서들이 원을 그리며 서있고

홀수번째 턴에는 12시방향의 댄서와 시계방향으로 옆에있는 댄서가 자리를 바꾼다.

짝수번째 턴에는 12시방향의 댄서와 반시계방향으로 옆에있는 댄서가 자리를 바꾼다. (나머지 댄서도 모두)

그래서 결국 K번 댄서의 양 옆에 있는 댄서 번호를 출력해야 한다.

배열과 mod연산자를 이용해서 풀었당.

코드

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dancers;
        int D, K, N;
        int d, k = 0;
        int index = 1;
        int T = sc.nextInt(); //the number of test cases
        
        while(T-- > 0){
            D = sc.nextInt();
            K = sc.nextInt();
            N = sc.nextInt();
            
            dancers= new int[D];
            for(int i = 0; i < D; i++)//초기화
                dancers[i] = i+1;
            
            for(int i = 0; i < N; i++){
                d = D/2;  //두명씩 짝
                for(int j = i; d-- > 0;)//총 d쌍이 서로 자리바꿈
                    swap(dancers, (j++)%D, (j++)%D);
            }
            
            for(int i = 0; i < D; i++)
                if(dancers[i] == K){k = i; break;}
            
            
            System.out.println("");
            System.out.print("Case #" + index++ + ": ");
            System.out.print(dancers[(k+1)%D] + " " + dancers[(k+D-1)%D] );
            
        }//end while
    }
    
    static void swap(int[] arr, int i, int j){
        int temp;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}