問題一覧 > 通常問題

No.1831 Parasol

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 86
作問者 : rianoriano / テスター : nok0nok0 👑 ygussanyygussany
13 ProblemId : 7390 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-10 19:12:45

問題文

あなたの手元には $2N-1$ 色の布があり、$1\leq i\leq 2N-1$ である整数 $i$ について、色 $i$ の布は $i$ 枚あります。 あなたはこの布を使って riano 君にパラソルを作ってあげることにしました。 持っている布の中から、異なる $N$ 色の布を $1$ 枚づつ使うとパラソルを作ることができます。

ただし riano 君は、同じ色遣いばかりだとつまらないと思っているため、 同じ配色の(厳密には、使われている色の集合が同じ)パラソルはそれぞれ $2$ 本までしか受け取りたくないと考えています。 あなたは最大で何本のパラソルを riano 君にあげられるでしょうか。 また、その際に作ったパラソルの配色も合わせて答えてください。

入力

$N$

  • $2\leq N \leq 300$
  • 入力は全て整数である

出力

$1$ 行目に、条件を満たして作ることのできるパラソルの本数の最大値を出力してください。
$2$ 行目以降の各行には、各パラソルに使った色を表す番号を $N$ 個、空白区切りで出力してください。条件を満たす配色であれば、どのようなものをどのような順で出力しても構いません。 ただし、riano 君に渡せないパラソルは出力に含めないでください。すなわち、$1$ 行目に出力する答えが $m$ であるとき、出力は全部で $m+1$ 行となるようにしてください。
最後に改行してください。

サンプル

サンプル1
入力
3
出力
5
1 4 5
2 3 5
2 4 5
3 4 5
4 3 5

あなたは $5$ 本のパラソルを出力のような配色で作りました。 $4$ 本目と $5$ 本目の配色は同じですが、他のパラソルの配色はすべて異なるため、同じ配色のパラソルはそれぞれ $2$ 本以下であり riano 君の条件を満たしています。 また、布は全部で $1+2+3+4+5=15$ 枚ありますが、全て使い切っているためこの本数が最大です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。