Cycles

题面翻译

题目描述

构造一个无向图（没有自环），使这个无向图恰好有 $m$ 个三元环，输出这个无向图的 $01$ 矩阵。

$($无向图的顶点数不超过 $100,1 \leq m \leq 10^5)$

输入输出格式

输入格式：

一行一个整数 $m$ 。

输出格式：

第一行为无向图的顶点数 $n$，接下来 $n$ 行为这个无向图的 $01$ 矩阵，不需要输出空格。

题目描述

John Doe started thinking about graphs. After some thought he decided that he wants to paint an undirected graph, containing exactly $k$ cycles of length $3$ .

A cycle of length $3$ is an unordered group of three distinct graph vertices $a$ , $b$ and $c$ , such that each pair of them is connected by a graph edge.

John has been painting for long, but he has not been a success. Help him find such graph. Note that the number of vertices there shouldn't exceed $100$ , or else John will have problems painting it.

输入格式

A single line contains an integer $k$ ( $1<=k<=10^{5}$ ) — the number of cycles of length $3$ in the required graph.

输出格式

In the first line print integer $n$ ( $3<=n<=100$ ) — the number of vertices in the found graph. In each of next $n$ lines print $n$ characters "0" and "1": the $i$ -th character of the $j$ -th line should equal "0", if vertices $i$ and $j$ do not have an edge between them, otherwise it should equal "1". Note that as the required graph is undirected, the $i$ -th character of the $j$ -th line must equal the $j$ -th character of the $i$ -th line. The graph shouldn't contain self-loops, so the $i$ -th character of the $i$ -th line must equal "0" for all $i$ .

样例 #1

样例输入 #1

1

样例输出 #1

3
011
101
110

样例 #2

样例输入 #2

10

样例输出 #2

5
01111
10111
11011
11101
11110