B - Set of Integers Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

足し算と引き算が苦手なきつねのために，うさぎが N^2 マス計算の問題を作ろうとしています．

うさぎは，準備の手間を考えて足し算と引き算の両方で同じ数の集合を使うことにしました．

計算の答えの種類が多いほうがより練習になりそうなので，足し算と引き算のうち，きつねがより苦手そうな方で答えの種類が多くなるようにしたいです．

問題文

正整数 N と，(不)等号 \mathrm{op} (<, =, > のうちいずれか) が与えられる．

以下のすべての条件を満たす集合 X が存在するか判定し，存在するならば 1 つ構成せよ．

  • X の各要素は 0 以上 10^9 以下の非負整数である．
  • |X| = N． (ただし |X| で集合 X の要素数を表す)
  • S = \{ a + b \mid a, b \in X \}, D = \{ a - b \mid a, b \in X \} としたとき |S|\ \mathrm{op}\ |D| が成り立つ．
    • すなわち，S, D はそれぞれ X の要素どうしの和/差としてありうる値の集合である．上の定義では a = b の場合も含むことに注意せよ．(以下の例も参考にせよ)

たとえば X = \{2, 0, 1, 9\} のとき S = \{0, 1, 2, 3, 4, 9, 10, 11, 18\} および D = \{-9, -8, -7, -2, -1, 0, 1, 2, 7, 8, 9\} なので，|S| < |D| である．

制約

  • 1 \leq N \leq 2\,019．
  • \mathrm{op} は <, =, > のうちいずれか．

入力

N \mathrm{op}

出力

条件を満たす集合が存在する場合，そのような集合を 1 つ出力せよ．集合はその要素を空白区切りで出力すること．

条件を満たす集合が存在しない場合は，かわりに Merry Christmas! とだけ出力せよ．

入力例 1

4 <

出力例 1

2 0 1 9

問題文に書かれている例である．

入力例 2

4 >

出力例 2

Merry Christmas!