A - Find the Array
cpcodeforcesdiv2greedymath
最終更新日
問題
https://codeforces.com/contest/1550/problem/A
問題文
n 個の正整数からなる数列 a は、以下の条件を満たすとき beautiful と呼ばれる。
すべての i に対して、 ai=1 であるか、 ai−1 か ai−2 が a に存在する。
s が与えられるので、 ∑ai=s となるような beautiful な数列 a の長さの最小値は?
制約
- 1≤t≤5000
- 1≤s≤5000
サンプル
4
1
8
7
42
1
3
3
7
考察
n 個の要素からなる数列の総和の最大値は、 {1,3,5,⋯,2n−1} のとき n2。
逆に考えれば、 s が与えられたとき、 ⌈s⌉ が答え。
最後の要素は 1 から 2n−1 まで動かせるから、 (n−1)2+1 から (n−1)2+(2n−1)=n2 までの範囲を表すことができる。
コード
https://codeforces.com/contest/1550/submission/122475672
制約が比較的小さいので、これで誤差なく通せる。
void solve() {
int n;
cin >> n;
cout << ceil(sqrt(n)) << endl;
}