NextFloor

すきな物やモノに囲まれて生きていく!

『Hanafuda Shuffle』

こちらの問題を解いてみました。
http://www.deqnotes.net/acmicpc/1978/ja


◆実行結果
5 2
1,2,3,4,5,
3 1
1,2,4,5,3,
3 1
1,2,5,3,4,
4
10 3
1,2,3,4,5,6,7,8,9,10,
1 10
1,2,3,4,5,6,7,8,9,10,
10 1
2,3,4,5,6,7,8,9,10,1,
8 3
5,6,7,8,9,10,1,2,3,4,
4
0 0
Program ended with exit code: 0


◆ソース

#include<stdio.h>

#define GMAX 51

void cardprint(int card[], int n)
{
    int i;
    for(i = 1; i <= n; i++){
        printf("%d,", card[i]);
    }
    printf("\n");
    return;
}

int main(int argc, const char * argv[])
{
    int card[GMAX], temp[GMAX];
    int i, j, k;
    int n, r, p, c;
    
    while(1){
        scanf("%d %d", &n, &r);
        if(n == 0 && r == 0){
            break;
        }
    
        for(i = 1; i < GMAX; i++){
            card[i] = i;
        }
        cardprint(card, n);
    
        for(i = 0; i < r; i++){
            scanf("%d %d", &p, &c);
            for(j = 0; j < c; j++){
                temp[j] = card[n-p-j+1];
            }
            for(j = n-p+2, k = n-p-c+2; j <= n; j++, k++){
                card[k] = card[j];
            }
            for(j = 0; j < c; j++){
                card[n-j] = temp[j];
            }
            cardprint(card, n);
    
        }
        printf("%d\n", card[n]);

    }
    
    return 0;
}


◆考え方
①山札の並びを配列として考える。
②山札の一番上を配列の左端か右端に設定する
③設定できたら山札の各札へ順番に番号をふる
④後は設定された山札の数から指定された回数だけカットする
⑤山札のカットについて
 1. カットは山札から指定した枚数だけ取り除く
 2. 取り除いた枚数だけ山札を圧縮する
 3. 圧縮した山札の上に取り除いたカードを順番に重ねる
 この3つの行為で山札がカットできる