問題一覧 > 通常問題

No.1422 Social Distance in Train

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 190
作問者 : 👑 koboshikoboshi / テスター : KazunKazun
2 ProblemId : 5074 / 出題時の順位表
問題文最終更新日: 2021-03-16 15:56:21

問題文

$N$ 人がけの座席に、どの $2$ 人も隣り合わないように $\left\lceil\frac{N}{2}\right\rceil$ 人が座るとき、席の埋まっている状態は何通りあるでしょうか。

以下はより厳密な問題文です。$N$ 人がけの座席があり、席には $1,2,\ldots,N$ と番号がついています。$i=1,2,\ldots,N-1$ に対し、番号 $i$ の席と番号 $i+1$ の席は隣り合っています。$\left\lceil\frac{N}{2}\right\rceil$ 人が $N$ 個の席のうちのいずれかに座ります。どの $2$ 人も同じ席または隣り合った席を選ぶことはできません。このとき、席の埋まっている状態は何通りあるでしょうか。ただし $2$ つの状態が異なるとは、一方では席 $i$ に座っている人がいるがもう一方では席 $i$ に座っている人がいないような番号 $i$ が存在することをいいます。

なお、$\left\lceil\frac{N}{2}\right\rceil$ は $\frac{N}{2}$ 以上の最小の整数を表します。

入力

$N$

$N$ は $1$ 以上 $10^9$ 以下の整数です。

出力

席の埋まっている状態が何通りあるかを求めて出力してください。最後に改行してください。

サンプル

サンプル1
入力
2
出力
2

$2$ 人がけの座席に $1$ 人が座るとき、「$1$ 番目の席が埋まっている」「$2$ 番目の席が埋まっている」 $2$ 通りがあります。

サンプル2
入力
5
出力
1

$5$ 人がけの座席に $3$ 人が座るとき、「$1,3,5$ 番目の席が埋まっている」 $1$ 通りのみです。席が埋まっているかどうかのみを考慮し、誰が座っているかは考慮しないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。