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.
Input
A single line contains an integer k (1 ≤ k ≤ 105) — the number of cycles of length 3 in the required graph.
Output
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.
Examples
input
1
output
3
011
101
110
input
10
output
5
01111
10111
11011
11101
11110
Solution:
#include <iostream> #include <iomanip> #include <stdio.h> #include <set> #include <vector> #include <map> #include <cmath> #include <algorithm> #include <memory.h> #include <string> #include <sstream> using namespace std; int n, i, j, k; int a[111][111]; int main() { scanf("%d",&n); memset(a,0,sizeof(a)); int m = 0; while (n > 0) for (i=100;i>=3;i--) if (i*(i-1)*(i-2)/6 <= n) { m += i; for (j=m-i;j<m;j++) for (k=m-i;k<m;k++) a[j][k] = (j != k); n -= i*(i-1)*(i-2)/6; for (int z=i;z>=2;z--) if (z*(z-1)/2 <= n) { m++; for (j=m-z-1;j<m-1;j++) a[j][m-1] = a[m-1][j] = 1; n -= z*(z-1)/2; for (int y=z+1;y>=2;y--) if (y*(y-1)/2 <= n) { m++; for (j=m-y-1;j<m-1;j++) a[j][m-1] = a[m-1][j] = 1; n -= y*(y-1)/2; break; } break; } break; } printf("%d\n",m); for (i=0;i<m;i++) { for (j=0;j<m;j++) printf("%d",a[i][j]); printf("\n"); } return 0; }