[Java] UVa 10978 Let’s Play Magic!

題目連結

題意:
環狀排列的牌，玩法是每次根據"指令的字母數"移動若干步
走到一張目標牌並移除，一直到最後
這題給你所有指令與拿走的牌，要問原始的牌順序為何

輸入測資先給定 N 張牌
接著 N 行依序是牌的名稱與指令 (第 N 個指令拿走最後一張牌)
輸出則為原本的牌(按順序列出名稱)

如範例測資:

原始有13張牌
QH 4C AS 8D KH 2S 7D 5C TH JH 3S 6C 9D

第一個指令是ACE(3步)，會拿走AS，也就是第3個位置是AS

拿走AS後長這樣 :
QH 4C 8D KH 2S 7D 5C TH JH 3S 6C 9D

第二個指令是TWO(3步)，繼續走3步，會拿走2S，也就是"原本的"第6個位置是2S

拿走後長這樣 :
QH 4C 8D KH 7D 5C TH JH 3S 6C 9D

第三個指令THREE(5步)，拿走3S後:
QH 4C 8D KH 7D 5C TH JH 6C 9D

第四個指令FOUR(4步)，從6C開始，到9D後會從頭QH開始，拿走4C

QH 8D KH 7D 5C TH JH 6C 9D

依此類推...

解法:
要根據指令重建序列
已知的是會從頭開始
根據指令重建即可
配合一個布林陣列，如果已經移除的改成true
下次走訪就直接略過

例如要走3步，第3步遇到已經移除的
就依序往下找

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	while (sc.hasNext()) {
	int N = Integer.valueOf(sc.next());
	if (N == 0)
	break;
	boolean left[] = new boolean[N];
	String list[] = new String[N];
	int index = -1;
	for (int n = 0; n < N; n++) {
	String card = sc.next();
	int order = sc.next().length();
	for (int i = 0; i < order; i++) {
	do {
	index = (index == N-1) ? 0 : (index + 1);
	} while (left[index]);
	}
	left[index] = true;
	list[index] = card;
	}
	System.out.print(list[0]);
	for (int s = 1; s < N; s++)
	System.out.print(" " + list[s]);
	System.out.println();
	}
	}
	}

view raw UVa10978.java hosted with ❤ by GitHub