yukicoder No.897 compαctree
一問ずつ記事をかくのはどうなのか?という思いもある。
問題
少し図を書いて考察すればすぐに規則がわかる。
N = 41, K = 3として考えてみる。
深さを最小にしたいので,各頂点に対する子の数はK個とするのが最良である。
図からわかるように,
深さ0のとき,頂点数は1個
深さ1のとき,頂点数は3個
深さ2のとき,頂点数は9個
深さ3のとき,頂点数は27個
であり,K倍ずつになっている。これの和がNを初めて超える深さを求めればよい。
Kのべき乗で増えていく,つまりどんどん増えるので単純にKのべき乗の和を計算して,Nを超えたときの深さを素直に出力すればOK。
K=1のときだけ少し注意。
Q = int(input()) for i in range(Q): N,K = map(int,input().split()) if K == 1: print(N-1) else: ans = 1 i = 1 while ans < N: ans += K**i if ans >= N: print(i) break i += 1
おまけ
高校数学の知識を覚えている人がいれば,以下のように考えても問題を言い換えてもよい。
初項1,公比の等比数列の第項までの和 を満たす最小のを求める。
不等式を変形して
を満たす最小のを求めればよいことになるので,
pythonのmathモジュールmath --- 数学関数 — Python 3.8.1 ドキュメント
が使える環境であれば以下のようにしてもよい。
import math Q = int(input()) for i in range(Q): N,K = map(int,input().split()) if K == 1: print(N-1) else: print(int(math.log(N*(K-1)+1,K)))