Universal Cup Judging System

Universal Cup

Limite de temps : 3.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Như đã biết, bài toán APSP (Đường đi ngắn nhất giữa mọi cặp đỉnh) có mối liên hệ sâu sắc với phép nhân ma trận min+. Hôm nay, chúng tôi muốn bạn giải quyết bài toán sau:

Cho $x$, hãy dựng một đồ thị vô hướng không trọng số liên thông (tức là mọi cạnh đều có trọng số bằng 1) sao cho $\sum_{i=1}^{n} \sum_{j=i+1}^{n} \operatorname{dis}(i, j) = x$. Ở đây, $\operatorname{dis}(i, j)$ biểu thị độ dài đường đi ngắn nhất giữa đỉnh $i$ và đỉnh $j$.

Bài toán này tất nhiên rất đơn giản... Đáng tiếc là tài nguyên của bạn có hạn, vì vậy bạn mong muốn tìm được một đồ thị có không quá 85 đỉnh thỏa mãn yêu cầu.

Dữ liệu vào

Một bộ kiểm tra duy nhất chứa nhiều bộ dữ liệu.

Dòng đầu tiên của dữ liệu vào là số lượng bộ dữ liệu $T$ ($1 \le T \le 2000$), biểu thị số bộ dữ liệu có trong bộ kiểm tra này.

Với mỗi bộ dữ liệu, có một dòng chứa một số nguyên $x$ ($1 \le x \le 10^5$), biểu thị ràng buộc cần thỏa mãn. Đảm bảo tồn tại ít nhất một đồ thị có không quá 85 đỉnh thỏa mãn điều kiện.

Kết quả

Với mỗi bộ dữ liệu, in ra số đỉnh $n$ mà bạn đã sử dụng trên dòng đầu tiên ($2 \le n \le 85$). Sau đó in ra $n - 1$ dòng, trong đó dòng thứ $i$ là một xâu nhị phân độ dài $n - i$. Ký tự thứ $j$ của dòng thứ $i$ là 1 khi và chỉ khi có cạnh nối giữa đỉnh $i$ và đỉnh $i + j$.

Ví dụ

Dữ liệu vào

4
1
3
6
8

Kết quả

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.