A - Find the Array

cpcodeforcesdiv2greedymath

最終更新日

Table of Contents

Loading...

問題

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 の長さの最小値は?

制約

サンプル

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; }