Asa's Website

問題

$n$ 個の正整数からなる数列 $a$ は、以下の条件を満たすとき beautiful と呼ばれる。

すべての $i$ に対して、 $a_i = 1$ であるか、 $a_i - 1$ か $a_i - 2$ が $a$ に存在する。

$s$ が与えられるので、 $\sum a_i = s$ となるような beautiful な数列 $a$ の長さの最小値は？

$n$ 個の要素からなる数列の総和の最大値は、 $\{ 1, 3, 5, \cdots, 2n - 1 \}$ のとき $n^2$ 。
逆に考えれば、 $s$ が与えられたとき、 $\lceil \sqrt{s} \rceil$ が答え。

最後の要素は $1$ から $2n - 1$ まで動かせるから、 $(n-1)^2 + 1$ から $(n-1)^2 + (2n - 1) = n^2$ までの範囲を表すことができる。

制約が比較的小さいので、これで誤差なく通せる。


void solve() {
  int n;
  cin >> n;
  cout << ceil(sqrt(n)) << endl;
}