Prove Him Wrong-Codeforces

投稿日：2022/04/02 更新日:2022/04/02

問題

$n$ 個の整数列 $a$ に対し以下の操作を行います。

2つの組 $i, j$ を選ぶ $(i \neq j)$
$a_i = a_j = |a_i - a_j|$ とする

どの $(i, j)$ を選んで操作を行ったとしても総和が減少しない（等しいまま、もしくは増加する） $n$ 個の整数列 $a,(1 \leqq a_i \leqq 10^9)$ を作成できるか判定してください。
作成可能ならば出力してください。

解法

総和が減少しないということは以下の不等式を満たします。
$a_i \geqq a_j$ とする。

\begin{aligned} a_i + a_j &\leqq 2(a_i - a_j)\\ a_i + a_j &\leqq 2a_i - 2a_j\\ 3a_j &\leqq a_i \end{aligned}

となり、各ペアが3倍以上の差があれば良いことが分かります。
後は $10^9$ より大きくならないように数列を作成していけば良いです。

実装

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> ans;

    const int limit = 1e9;
    long long pow3 = 1;
    for(int i = 0;i < n; ++i){
        if(pow3 > limit){
            cout << "NO" << endl;
            return;
        }
        ans.push_back(pow3);
        pow3 *= 3;
    }

    cout << "YES" << endl;
    cout << ans[0];
    for(int i = 1;i < n; ++i){
        cout << " " << ans[i];
    }
    cout << endl;
}

int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}