AOJ-1129 POJ-1978: Hanafuda Shuffle

問題概要

最初に順番に積まれたトランプがある。ある方法でシャッフルを繰り返した時に、一番上にどれがくるかを求める問題。

解法

普通にシミュレーションしても通る。この手のシャッフルする問題を解くテクニックに、逆向きにシミュレーションして、終了時一番上にあったカードが開始時どこにあったかをシミュレーションする方法がある。普通にシミュレーションするのに比べて何がうれしいかというと、シミュレーション時に移動するカードが1枚だけでいいというのがとてもありがたい。

import java.util.*;

public class Main {
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		while(true){
			int n = in.nextInt(), r = in.nextInt();
			if(n==0 && r==0) return ;
			int ps[] = new int[r], cs[] = new int[r];
			for(int i=r-1; i>=0; i--){
				ps[i] = in.nextInt();
				cs[i] = in.nextInt();
			}
			int pos = n;
			for(int i=0; i<r; i++){
				if(n-pos+1 <= cs[i]){
					pos -= ps[i] - 1;
				}
				else if(n-pos+1 < cs[i] + ps[i]){
					pos += cs[i];
				}
			}
			System.out.println(pos);
		}
	}
}