Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

A. Omkar and Completion (Codeforces Round #655 Div. 2)

This is the GAG of Codeforces!

問題

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

問題概要

正数nが与えられる。長さnの配列を以下の条件を満たすように構築せよ。

  • 各項は1000を超えない正数である
  •  x,y,z (1 \leq x,y,z \leq n)に対してa_x+a_y \neq a_zを満たす(ただしx,y,zは重複が許される)

考察

結論からいうと、1をn個並べればよいです。なんだそれ

1番目の条件は明らかに満たしますし、2番目の条件についても、どの2つの項をとってもその和は2で、1にならないので条件を満たします。

もう少し一般的には、すべての項を1000以下の奇数にすれば条件が満たせます。どの2つの項をとってもその和は(奇数+奇数なので)偶数で、奇数にならないからです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) cout << "1" << (i == n - 1 ? '\n' : ' ');
    }
}