Flip and Shift (UVa Live Archive Asia - Site 4 (Korea) - 2001/2002 Taejon (Korea))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=2325

問題

図にあるようにフリップの操作とシフトの操作ができるトラックが存在する。黒のディスクと白のディスクを分離できるか？
10<=トラックの長さ<=30

解法

よく見るとフリップの操作は1つ飛ばしのスワップになっている。なので長さが奇数の場合は一周させれば隣との交換ができることになるので常に分離可能。長さが偶数の場合は奇数(偶数)番目の位置同士は任意の位置に移動可能なので、奇数番目に出てくる黒いディスクと偶数番目に出てくる黒いディスクの個数の差が1以下になっていれば分離可能。