A - Find the Array

問題

https://codeforces.com/contest/1550/problem/A (新しいタブで開く)

問題文

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

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

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

制約

• $1 \le t \le 5000$
• $1 \le s \le 5000$

サンプル

4
1
8
7
42

1
3
3
7

考察

$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$ までの範囲を表すことができる。

コード

https://codeforces.com/contest/1550/submission/122475672 (新しいタブで開く)

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

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