問題一覧 > 通常問題

No.3012 岩井星人グラフ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 225
作問者 : 👑 loop0919 / テスター : 高橋ゆに 👑 binap eom2357 DeltaStruct Apollo@Kuro Yama.can こめだわら のらら あじゃじゃ
5 ProblemId : 11545 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-01-25 13:27:22

問題文

$3$ 以上の整数 $X, Y$ が与えられます。以下のように説明される腕の本数 $X,$ 腕の長さ $Y$ の岩井星人グラフを $1$ つ出力してください。

  • $XY$ 個の頂点と $XY$ 本の辺からなる単純無向グラフである。
  • 次数 $1$ の頂点が $X$ 個、次数 $2$ の頂点が $X (Y - 2)$ 個、次数 $3$ の頂点が $X$ 個ある。
  • 任意の次数 $1$ の頂点 $v$ について、頂点 $v$ からの距離が最も短い次数 $3$ の頂点との距離が $Y - 1$ である。

具体例は下記のサンプルを参考にしてください。

ただし、本問題の制約下ではそのような岩井星人グラフは複数存在しますが、それらのいずれを出力しても正解と判定されます。

単純無向グラフとは

単純無向グラフとは、単純で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

次数とは

頂点の次数とは、その頂点から出ている辺の本数のことをいいます。

制約

  • $3 \le X, Y \le 500$
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$X$ $Y$

出力

答えとなる腕の本数 $X, $ 腕の長さ $Y$ の岩井星人グラフが以下のように説明されるとする。

  • $n$ 個の頂点からなり、各頂点には $1$ から $n$ までの番号が振られている。
  • $m$ 本の辺からなり、各辺には $1$ から $m$ までの番号が振られている。
  • 各 $i ~ (1 \le i \le m)$ について、辺 $i$ は頂点 $u_i$ と頂点 $v_i$ を結ぶ。

このとき、以下の形式で出力せよ。ただし、本問題の制約下では答えが複数存在するが、それらのいずれを出力しても正解と判定される。

$n$ $m$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{m}$ $v_{m}$

サンプル

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

以下のようなグラフが腕の本数 $3,$ 腕の長さ $3$ の岩井星人グラフの一例です。

このグラフについて、以下のことがいえます。ここで、$X = 3, ~ Y = 3$ です。

  • $9$ 個の頂点と $9$ 本の辺からなる単純無向グラフである。$(XY = 9)$
  • 次数 $1$ の頂点は、頂点 $1, 2, 3$ の $3$ 個 $(X = 3)$ ある。
  • 次数 $2$ の頂点は、頂点 $4, 5, 6$ の $3$ 個 $(X(Y - 2) = 3)$ ある。
  • 次数 $3$ の頂点は、頂点 $7, 8, 9$ の $3$ 個 $(X = 3)$ ある。
  • それぞれの次数 $1$ の頂点について、以下のことが言える。
    • 頂点 $1$ との距離が最も短い、次数 $3$ の頂点は頂点 $8$ である。その距離は $2 ~ (Y - 1 = 2)$ である。
    • 頂点 $2$ との距離が最も短い、次数 $3$ の頂点は頂点 $9$ である。その距離は $2$ である。
    • 頂点 $3$ との距離が最も短い、次数 $3$ の頂点は頂点 $7$ である。その距離は $2$ である。
サンプル2
入力
5 4
出力
20 20
1 2
1 5
1 6
2 3
2 9
3 4
3 12
4 5
4 15
5 18
6 7
7 8
9 10
10 11
12 13
13 14
15 16
16 17
18 19
19 20

以下のようなグラフが腕の本数 $5,$ 腕の長さ $4$ の岩井星人グラフの一例です。

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