Fox and Minimal path (Codeforces 388B)
Tags: Implement, bitmasks

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 Gij 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: Gii = 'N' and Gij = Gji 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. 

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.

Sample Inputs:
2

9

1

Sample Outputs:
4
NNYY
NNYY
YYNN
YYNN

8
NNYYYNNN
NNNNNYYY
YNNNNYYY
YNNNNYYY
YNNNNYYY
NYYYYNNN
NYYYYNNN
NYYYYNNN

2
NY
YN

Solution (Python):
k = bin(int(input()))[2:]
n = len(k)
m = n * 3 + 1
g = [['N'] * m for _ in range(m)]

def add(u, v):
    u %= m
    v %= m
    g[u][v] = g[v][u] = 'Y'
add(1, 2)
add(1, 3)
for i in range(1, n):
    add(3 * i - 1, 3 * i + 2)
    add(3 * i - 1, 3 * i + 3)
    add(3 * i, 3 * i + 2)
    add(3 * i, 3 * i + 3)
    add(3 * i + 1, 3 * i + 4)
for (i, x) in enumerate(k[::-1]):
    if x == '1':
        add(3 * i + 3, 3 * i + 4)
print(m)
for it in g:
    print(*it, sep='')

Solution (Python):
(n, m) = (337, int(input()))
p = [['N'] * n for i in range(n)]

def f(i, j):
    p[i][j] = p[j][i] = 'Y'
k = 6 + 15 * 5
for j in range(2, 6):
    f(1, j)
for i in range(6, k, 5):
    for j in range(i - 4, i):
        f(i, j)
    for j in range(i + 1, i + 5):
        f(i, j)
(q, d, s) = (4 ** 15, 0, k)
while q:
    if m >= q:
        t = m // q
        m -= t * q
        if d == 0:
            for j in range(k - t, k):
                f(0, j)
        else:
            f(0, s)
            for i in range(s, s + d):
                f(i, i + 1)
            s += d
            for j in range(k - t, k):
                f(s, j)
            s += 1
    k -= 5
    d += 2
    q //= 4
print(s)
for i in range(s):
    print(''.join(p[i][:s]))

Solution (Python):
k = str(input())
l = len(k)
paths = []
for i in range(l):
    paths.append([1] * i + [int(k[i])] + [10] * (l - i - 1))
lens = [sum(p) for p in paths]
n = sum(lens) + 2
m = [''] * n
m[0] = 'N' * 2
for i in range(len(paths)):
    m[0] += 'Y' * paths[i][0] + 'N' * (lens[i] - paths[i][0])
m[1] = 'N'
for i in range(len(paths)):
    m[1] += 'N' * (lens[i] - paths[i][-1]) + 'Y' * paths[i][-1]
ind = 2
for p in paths:
    for i in range(len(p) - 1):
        for j in range(p[i]):
            m[ind] = 'N' * (p[i] - j) + 'Y' * p[i + 1] + 'N' * n
            ind += 1
    for j in range(p[-1]):
        m[ind] = 'N' * n
        ind += 1
m2 = [''] * n
for i in range(n):
    m2[i] = ''
    for j in range(i):
        m2[i] += m2[j][i]
    m2[i] += m[i][:n - i]
print(len(m2))
for s in m2:
    print(s)