Universal Cup Judging System

Universal Cup

Time Limit: 3.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

よく知られているように、APSP(全点対最短経路)問題は min+ 行列積と深い関わりがあります。今日、あなたに解いてほしい問題は以下の通りです。

$x$ が与えられるので、$\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$ を満たす無向重みなし連結グラフ(すなわち、すべての辺の重みが 1 であるグラフ)を構築してください。ここで、$\operatorname{dis}(i, j)$ は頂点 $i$ と頂点 $j$ の間の最短経路長を表します。

この問題は非常に簡単です……残念ながら、あなたのリソースは限られているため、頂点数が 85 以下の条件を満たすグラフを見つける必要があります。

入力

1 つのテストケースには複数のデータセットが含まれます。

入力の 1 行目はデータセットの個数 $T$ ($1 \le T \le 2000$) であり、このテストケースに含まれるデータセットの数を表します。

各データセットについて、満たすべき制約を表す整数 $x$ ($1 \le x \le 10^5$) が 1 行に与えられます。条件を満たす頂点数 85 以下のグラフが少なくとも 1 つ存在することが保証されます。

出力

各データセットについて、1 行目に使用した頂点数 $n$ ($2 \le n \le 85$) を出力してください。続いて $n - 1$ 行を出力し、そのうち $i$ 行目には長さ $n - i$ の 2 進文字列を出力してください。$i$ 行目の $j$ 番目の文字は、頂点 $i$ と頂点 $i + j$ の間に辺が存在するとき、かつそのときに限り 1 となります。

入出力例

入力

4
1
3
6
8

出力

2
1
3
11
1
4
111
11
1
4
110
10
1

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.