Universal Cup Judging System

Universal Cup

حد الوقت: 3.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Wie allgemein bekannt ist, steht das APSP-Problem (Kürzeste Pfade zwischen allen Paaren) in engem Zusammenhang mit der min+-Matrizenmultiplikation. Heute möchten wir, dass du das folgende Problem löst:

Gegeben sei $x$. Konstruiere einen ungerichteten, ungewichteten zusammenhängenden Graphen (d. h., alle Kantengewichte sind 1), sodass $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$ gilt. Hierbei bezeichnet $\operatorname{dis}(i, j)$ die Länge des kürzesten Pfades zwischen Knoten $i$ und Knoten $j$.

Dieses Problem ist sicherlich sehr einfach ... Leider sind deine Ressourcen begrenzt, sodass du einen Graphen mit höchstens 85 Knoten finden möchtest, der die Anforderungen erfüllt.

Eingabe

Ein einzelner Testfall enthält mehrere Datensätze.

Die erste Zeile der Eingabe enthält die Anzahl der Datensätze $T$ ($1 \le T \le 2000$), die angibt, wie viele Datensätze in diesem Testfall enthalten sind.

Für jeden Datensatz gibt es eine Zeile mit einer ganzen Zahl $x$ ($1 \le x \le 10^5$), welche die zu erfüllende Bedingung darstellt. Es wird garantiert, dass mindestens ein Graph mit höchstens 85 Knoten existiert, der die Bedingung erfüllt.

Ausgabe

Gib für jeden Datensatz in der ersten Zeile die Anzahl der verwendeten Knoten $n$ aus ($2 \le n \le 85$). Gib anschließend $n - 1$ Zeilen aus, wobei die $i$-te Zeile eine Binärzeichenkette der Länge $n - i$ ist. Das $j$-te Zeichen der $i$-ten Zeile ist genau dann 1, wenn eine Kante zwischen Knoten $i$ und Knoten $i + j$ existiert.

Beispiel

Eingabe

4
1
3
6
8

Ausgabe

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.