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.
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.
本地的标准写法构造三进制
由于的是用二进制会有极限的数据卡你图的大小
暂时先把re代码发上来吧
留坑
#include<cstdio>
#include<map>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
bool mp[1005][1005];
int highbits(int x)
{
int cnt=0;
while(x)
{
cnt++;
x=x>>1;
}
return cnt-1;
}
int main()
{
memset(mp,0,sizeof(mp));
int n;
scanf("%d",&n);
int tmp;//取临时位
int pos=3;//记录矩阵目前状态
int bits=highbits(n);
tmp=n;
if(bits==0)
{
mp[1][2]=1;
}
for(int i=0; i<=bits; i++)
{
int temp=(tmp&1);
//cout<<"tmp"<<tmp<<" "<< temp <<endl;
//cout<<i<<endl;
if(temp==1)
{
//cout<<i<<endl;
int flag=0;
for(int j=1; j<=bits; j++)
{
if(j<=i)//构成二进制环形
{
if(j==1)
{
mp[1][pos]=1;
pos++;
mp[1][pos]=1;
}
else
{
mp[pos-2][pos]=1;
mp[pos-1][pos]=1;
pos++;
mp[pos-3][pos]=1;
mp[pos-2][pos]=1;
}
flag=1;
}
else
{
if(j==1)
{
mp[1][pos]=1;
}
else
{
if(flag==1)
{
mp[pos-1][pos]=1;
mp[pos-2][pos]=1;
}
else
mp[pos-1][pos]=1;
}
flag=0;
}
pos++;
}
if(i==bits)
{
mp[2][pos-2]=1;
mp[2][pos-1]=1;
}
else
{
mp[2][pos-1]=1;
}
}
tmp=tmp>>1;
}
for(int i=1; i<=1000; i++)
{
for(int j=1; j<=1000; j++)
{
if(i==j) mp[i][j]=0;
if(i>j) mp[i][j]=mp[j][i];
}
}
// for(int i=0;i<=9;i++)
// cout<<i;
// cout<<endl;
printf("1000
");
for(int i=1; i<=1000; i++)
{
//cout<<i%10;
for(int j=1; j<=1000; j++)
{
if(mp[i][j]==1)
{
printf("Y");
}
else
{
printf("N");
}
}
printf("
");
}
}
//caowenbo