Educational CF Round 111 A - Find the Array


Tags:cpcodeforcesdiv2greedymath

問題

https://codeforces.com/contest/1550/problem/A

問題文

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

すべての ii に対して、 ai=1a_i = 1 であるか、 ai1a_i - 1ai2a_i - 2aa に存在する。

ss が与えられるので、 ai=s\sum a_i = s となるような beautiful な数列 aa の長さの最小値は?

制約

  • 1t50001 \le t \le 5000
  • 1s50001 \le s \le 5000

サンプル

4
1
8
7
42
1
3
3
7

考察

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

最後の要素は 11 から 2n12n - 1 まで動かせるから、 (n1)2+1(n-1)^2 + 1 から (n1)2+(2n1)=n2(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;
}