問題一覧 > 通常問題

No.1571 All Your Cycles Are Same Lengths

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 31
作問者 : 👑 PCTprobabilityPCTprobability / テスター : blackyukiblackyuki
2 ProblemId : 6299 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-02-06 21:50:39

問題文

以下の条件を満たす $N$ 頂点 $\displaystyle \frac{N(N-1)}{2}$ 辺の無向単純グラフ、すなわち $N$ 頂点の完全グラフを構成してください。

  • 各辺のコストは $0$ 以上 $100$ 以下の整数である。
  • 頂点 $1$ から始まり全ての頂点を $1$ 回ずつ通って頂点 $1$ に戻ってくる時に通った辺全てのコストの和が必ず $T$ になる。

$Q$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

$Q$
$N_1 \quad T_1$
$N_2 \quad T_2$
$\vdots$
$N_Q \quad T_Q$
  • 入力は整数である。
  • $1 \le Q \le 200$
  • $2 \le N \le 8$
  • $0 \le T \le 100$

出力

$i$ 個目の解答を $S_i$ とした時、以下のように各テストケースの結果を改行区切りで出力してください。

$S_1$
$S_2$
$\vdots$
$S_Q$

各テストケースに対しては以下のように出力してください。

  • もし条件を満たすグラフが存在するならばYesと出力してください。続く $\displaystyle \frac{N(N-1)}{2}$ 行のうちの $i$ 行目には、$a_i \ b_i \ c_i$ と出力してください。これはグラフの $i$ 本目の辺が $a_i$ と $b_i$ をつないでいてコストが $c_i$ であることを表します。ただし以下の条件を満たさなくてはなりません。
    • $1 \le a_i < b_i \le N$
    • $i \neq j$ ならば $(a_i,b_i) \neq (a_j,b_j)$
    • $0 \le c_i \le 100$
    • 頂点 $1$ から始まり全ての頂点を $1$ 回ずつ通って頂点 $1$ に戻ってくる時に通った辺全てのコストの和が必ず $T$ になる。

  • 条件を満たすグラフが存在しないならばNoとのみ出力してください。

サンプル

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

出力されたグラフは全ての辺のコストが $1$ なので頂点 $1$ から始まり全ての頂点を $1$ 回ずつ通って頂点 $1$ に戻ってくる時に通った辺全てのコストの和は必ず $4$ になります。

また、その他の条件もすべて満たしているためこのグラフは条件を満たします。

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