B. Fox and Minimal path

题目连接：

http://codeforces.com/contest/388/problem/B

Description

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.

Sample Input

Sample Output

4

NNYY

NNYY

YYNN

YYNN

Hint

题意

你需要构造一个图，使得1到2的最短路恰好有k条

题解：

拆成二进制，比如9 = 2⁰⁺²3

二进制的最短路就非常好构造，就2*2*2这样去构造就好了

然而这样裸的构造的话，点数可能会超过1000个点

所以你再压缩一下点的个数，复用一下就好了

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3200;

int mp[maxn][maxn];

int k,bit[32],tot=3,max_len;

int getid()

{

    return tot++;

}

int main()

{

    scanf("%d",&k);

    int id1=1,id2=1,id3=getid();

    while(k)

    {

        if(k%2)mp[id1][id3]=1,mp[id2][id3]=1;

        k/=2;if(k==0)break;

        int id4=getid(),id5=getid(),id6=getid();

        mp[id1][id4]=1,mp[id1][id5]=1;

        mp[id2][id4]=1,mp[id2][id5]=1;

        mp[id3][id6]=1;

        id1=id4,id2=id5,id3=id6;

    }

    mp[id3][2]=1;

    int Max = getid()-1;

    printf("%d\n",Max);

    for(int i=1;i<=Max;i++,cout<<endl)for(int j=1;j<=Max;j++)

    if(mp[i][j]||mp[j][i])printf("Y");else printf("N");

}

巴特西

Codeforces Round #228 (Div. 1) B. Fox and Minimal path 构造