Universal Cup Judging System

Universal Cup

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

眾所周知,APSP(全點對最短路徑)問題與 min+ 矩陣乘法有著深刻的聯繫。今天,我們希望你解決以下問題:

給定 $x$,構造一個無向無權連通圖(即所有邊權均為 1),使得 $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$。這裡,$\operatorname{dis}(i, j)$ 表示節點 $i$ 與節點 $j$ 之間的最短路徑長度。

這個問題當然非常簡單……不幸的是,你的資源有限,因此你希望找到一個節點數不超過 85 且滿足要求的圖。

輸入格式

單個測試資料包含多組資料集。

輸入的第一行是資料集的數量 $T$ ($1 \le T \le 2000$),表示該測試資料中包含的資料集數量。

對於每組資料集,有一行包含一個整數 $x$ ($1 \le x \le 10^5$),表示需要滿足的限制條件。保證存在至少一個節點數不超過 85 的圖滿足條件。

輸出格式

對於每組資料集,在第一行輸出你使用的節點數 $n$ ($2 \le n \le 85$)。接著輸出 $n - 1$ 行,其中第 $i$ 行是一個長度為 $n - i$ 的二進位字串。第 $i$ 行的第 $j$ 個字元為 1 若且唯若節點 $i$ 與節點 $i + j$ 之間存在一條邊。

範例

輸入

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.