No.244 ★1のグラフの問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 586
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
0 ProblemId : 651 / 出題時の順位表
問題文最終更新日: 2016-05-17 23:45:13

問題文

グラフとは頂点と辺からなるデータ構造のことである。
頂点と頂点の間を辺で繋ぐことで頂点と頂点を結ぶことができる。
頂点と頂点を辺で繋いだ頂点間を自由に移動できる。

いま頂点が$N$個与えられる。
最初の状態ですべての頂点は辺で繋がっていない。
頂点と頂点を辺で繋ぐときのグラフのルールは次のようなものである。

・辺は必ず異なる頂点間を繋ぐ。
・同じ頂点と頂点の間に2本以上の辺は無い。

最初からある頂点の数$N$が与えられるので、
すべての頂点を移動できるように繋ぐ必要のある最少の辺の本数を答えよ。

入力

$N$

最初からある頂点の数$N$が与えられる。$2 \le N \le 13$。

出力

繋ぐ必要のある最少の辺の数を1行で出力せよ。
最後に改行すること。

サンプル

サンプル1
入力
2
出力
1

頂点0と頂点1の2個の頂点がある。
この2つの頂点を1つの辺で繋げば良い。

サンプル2
入力
4
出力
3

頂点0と頂点1と頂点2と頂点3がある。
例えば、頂点0と頂点1、頂点1と頂点2、頂点2と頂点3を繋ぐ方法がある。
別に、頂点0と頂点1、頂点1と頂点2、頂点1と頂点3を繋ぐ方法もある。
どちらにしろ繋ぐのに必要な辺の本数は3本である。

サンプル3
入力
13
出力
12

13個の頂点がある。
辺を繋いでできるグラフのパターンはたくさんあるが、
必要な最少の辺の本数は12本である。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。