問題の詳細は「円テーブルで席替え」(CodeIQ)を参照してください。
例えば、n のとき、最初に左図のように座っていると、右図のように席替えをすればすべての人の隣が変わることになります。
標準入力から が与えられたとき、席替えをして両隣の人が変わるような並び順は何通りあるかを求め、その数を標準出力に出力してください。
n のときは、上記以外に右図の左右を反転したパターンがありますので、標準出力に「2」を出力します。
私の回答にはよくあることですが、全パターン列挙で済ませてしまいました。
これを配列で表現すると初期状態は[0,1,2,,n-1]と並んでいるわけです。円になっているので最後の要素は最初の要素と隣り合っているとみなします。
そして、先生は固定なので実際は(1..n-1)の順列が並び順の全パターンで、これは362880通りしかないため全部列挙してチェックしても時間的に間に合います。
1〜n-1の値の配列の順列を列挙し、check()でチェックします。この時、0(先生)は固定なので最初の要素として、生成した並び順の先頭に追加します。
check()は正しい並び順なら1、違うなら0を返すので結果を加算して返却すれば答えになります。
l,rは現在チェックしている要素番号の左右の要素番号で、配列の先頭の左は末尾、末尾の右は先頭になるようにしています(5〜6行目)。
vl,vrは現在チェックしている値の並び替え前の値です。これも0より小さくなった場合はn-1、nになった場合は0にしています(8〜9行目)。
多分、再起を使ってOKなパターンを組み立てた方が早いと思いますが、計算量を見積もったら余裕っぽかったのでpermitation()を使って総当たりしてしまいました。