問題一覧 > 通常問題

No.1519 Diversity

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 86
作問者 : NatsubiSoganNatsubiSogan / テスター : MZKiMZKi aspiaspi NachiaNachia
4 ProblemId : 5891 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-12 20:04:01

問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点の単純無向グラフであって、その次数列の要素の種類数が最大となるようなものを $1$ つ構成してください。

備考

  • ある無向グラフ $G$ が 単純 であるとは、$G$ が自己ループや多重辺を持たないことを指します。
  • ある無向グラフ $G$ の 次数列 とは、$G$ の各頂点の次数を降順に並べた数列を指します。

入力

$N$

  • $N$ は $2 \leq N \leq 500$ を満たす整数

出力

以下のフォーマットで、構成したグラフを出力してください。出力はすべて整数でなければなりません。

$M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$
出力の $1$ 行目における $M$ はグラフの辺の数を表します。ただし、$0 \leq M \leq \frac{N(N-1)}{2}$ を満たす必要があります。

出力の $i+1\ (1 \leq i \leq M)$ 行目は、$i$ 番目の辺において、頂点 $u_i$ と $v_i$ が双方向に結ばれていることを表します。ただし、$1 \leq u_i,v_i \leq N$ を満たす必要があります。

辺は任意の順番で出力して構いません。

最後に改行してください。

サンプル

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

解の一例です。この場合、次数列は $(2,1,1)$ となり、この列の要素の種類数は $2$ です。これが $N=3$ での種類数の最大となります。

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