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$. $j$-й символ $i$-го рядка дорівнює 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.