読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Hanafuda Shuffle(PKJ No.1978)

Hanafuda Shuffle(PKJ No.1978)

n枚のカードが与えられて、下から1,2,...,nの番号が振られている。
 r, p_i, c_i (1\leq i \leq r)が与えられて、
上の p_i -1枚とその下の c枚を入れ替えるカットという操作をr回繰り返した後の一番上のカードの数字を求める。
制約
1 \leq n,r \leq 50
p+c \leq n-1

アルゴリズム

ただシミュレートするだけ。
アレイでデッキを表現して、1要素ずつサブアレイを取り出して交換するときは、コピーする順番を気を付ける。
STLとかを使えばサブリスト?を簡単に付け加えたり、削除したりできる。

コード

begin()のところがちょいと見にくい

#include <iostream>
#include <vector>
using namespace std;

int main(){
	int n, r, p, c;
	while( cin >> n >> r ){
		if( !n && !r ) break;
		vector<int> deck(n);
		for(int i=0; i<n; ++i) deck[i] = n-i;
		while( r-- ){
			cin >> p >> c;
			deck.insert(deck.begin(), deck.begin()+p-1, deck.begin()+p-1 + c);
			deck.erase(deck.begin()+c+p-1, deck.begin()+c+p-1 + c);
		}
		cout << deck.front() << endl;
	}

	return 0;
}

javaでは、indexで指定できるのでカット操作の部分は多少すっきりしている。
C++に慣れてると、subList()で返されるリストの変更が元のリストに反映されるのが非常に気持ち悪い。

import java.util.*;
public class pku1978 {
	static Scanner stdin;
	public static void main(String[] args) {
		stdin = new Scanner(System.in);
		new pku1978();
	}
	pku1978(){
		while(true){
			int n = stdin.nextInt();
			int r = stdin.nextInt();
			if( n == 0 && r == 0 ) break;
			
			LinkedList<Integer> deck = new LinkedList<Integer>();
			for(int i=0; i<n; ++i) deck.add(n-i);

			while(r-- != 0){
				int p = stdin.nextInt();
				int c = stdin.nextInt();
				deck.addAll(0, deck.subList(p-1, p-1+c));
				deck.subList(c+p-1, c+p-1+c).clear();
			}	
			System.out.println(deck.getFirst());
		}
	}
}