No.897 compαctree

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 171
作問者 : niuezniuez / テスター : Lemma299Lemma299
1 ProblemId : 3403 / 出題時の順位表
問題文最終更新日: 2019-10-04 21:31:43

問題文

niuez くんは木を美しく作る技術を持っており,美しい木を求める客から依頼を受けています.
niuez くんの住む街ではコンパクトな木(compactree)が流行っており,それを作成する query を niuez くんは大量に預かっています.
次の $Q$ 個の query を処理してください.

  • $N \ K$
    • $N$ 個の頂点と$N-1$個の辺からなる $K$ 分有向木(すべての頂点の子が高々 $K$ 個であるような木)のうち,深さの最小値を求める.
    • ここで,深さとは根から各頂点へのパスに含まれる辺の数のうち,最大のものを指します.

入力

$Q$
$N_0\ K_0$
$\cdots$
$N_{Q-1}\ K_{Q-1}$
  • $1 \leq Q \leq 10$
  • $1 \leq N_i, K_i \leq 10^9$
  • 入力はすべて整数

出力

$Q$ 行出力し,$i$ 行目には $i$ 番目の ${\rm query}$ の答えを整数で一行に出力してください.

サンプル

サンプル1
入力
3
4 2
41 3
100 1
出力
2
4
99

最初のクエリは例えば以下のように木をつくると高さを2にできます.
子の数は頂点$2$の2個が最大で, 入力の条件を満たしています.

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

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