Fox Ciel wants to write a task for a programming contest. The task is: “You are given a simple undirected graph with n vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2.”
Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to k?
Input
The first line contains a single integer k (1 ≤ k ≤ 109).
Output
You should output a graph G with n vertexes (2 ≤ n ≤ 1000). There must be exactly k shortest paths between vertex 1 and vertex 2 of the graph.
The first line must contain an integer n. Then adjacency matrix G with n rows and n columns must follow. Each element of the matrix must be ‘N’ or ‘Y’. If G ij is ‘Y’, then graph G has a edge connecting vertex i and vertex j. Consider the graph vertexes are numbered from 1 to n.
The graph must be undirected and simple: G ii = ‘N’ and G ij = G ji must hold. And there must be at least one path between vertex 1 and vertex 2. It’s guaranteed that the answer exists. If there multiple correct answers, you can output any of them.
Examples
input
2
output
4
NNYY
NNYY
YYNN
YYNN
input
9
output
8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN
input
1
output
2
NY
YN
Note
In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.
In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.
Solution:
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> using namespace std; char g[2010][2010]; int main() { int k; scanf("%d", &k); if (k == 1) { puts("2"); puts("NY"); puts("YN"); return 0; } int mx = 0; for (int j = 0; j < 30; j++) if (k & (1 << j)) { mx = j; } memset(g, 'N', sizeof(g)); int n = 2; int u = 1; for (int j = 1; j <= mx; j++) { n++; g[u][n] = g[n][u] = 'Y'; int x = n; n++; g[u][n] = g[n][u] = 'Y'; int y = n; int z; if (j == mx) { z = 2; } else { z = ++n; } g[x][z] = g[z][x] = 'Y'; g[y][z] = g[z][y] = 'Y'; u = z; } for (int j = mx - 1; j >= 0; j--) { if (k & (1 << j)) { int v = 3 * j + 2; if (j == 0) v--; int len = 2 * (mx - j); for (int it = 0; it < len - 1; it++) { n++; g[v][n] = g[n][v] = 'Y'; v = n; } g[v][2] = g[2][v] = 'Y'; } } printf("%d\n", n); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) putchar(g[i][j]); putchar('\n'); } return 0; }