No.690 E869120 and Constructing Array 4

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 46
作問者 : e869120e869120 / テスター : PulmnPulmn

2 ProblemId : 1686 / 出題時の順位表

問題文

以下のような条件を満たすグラフを 1 つ出力してください. (Array とは何なのか…)

  • $N$ 頂点 $M$ 辺の有向グラフであり, 辺 $i$ ($1 \leq i \leq M$) は頂点 $d1_i$ から $d2_i$ へ結ぶ. $d1_i < d2_i$ を満たす必要がある.
  • そのとき, 頂点 $1$ から $N$ に行く方法の通り数(頂点 $1$ を始点、頂点$N$ を終点とするパスの個数)はちょうど $K$ である.
  • $1 \leq N \leq 32$ を満たす必要がある. また, $i \neq j$ であれば, $d1_i \neq d1_j$ と $d2_i \neq d2_j$ のどちらかは満たしている必要がある.

入力

K

$1$ 行に, $0$ 以上 $10^{9}$ 以下の整数 $K$ が与えられる.

出力

$N$ $M$
$d1_1$ $d2_1$
$d1_2$ $d2_2$
...
$d1_M$ $d2_M$

$1$ 行目に, グラフの頂点数 $N$, 辺数 $M$ を出力すること.
$2$ 行目から $M$ 行にわたって, グラフの辺の情報を出力すること.
最後に改行をすること.

サンプル

サンプル1
入力
2
出力
3 3
1 2
1 3
2 3

1 -> 3, 1 -> 2 -> 3 の 2 通りの行き方があります.

サンプル2
入力
3
出力
5 6
1 2
2 3
3 4
4 5
1 5
2 4

サンプル3
入力
12
出力
9 15
1 2
1 3
2 3
2 4
2 8
3 5
4 6
4 7
5 6
5 7
5 8
6 8
6 9
7 9
8 9

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

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