CFR 389 D. Fox and Minimal path ( Binary Enumeration )

Problem - D - Codeforces

1 ≤ K ≤ 1e9

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

int K;
int G[ MAXN ][ MAXN ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> K;
if( K == 1 ){
cout << 2 << endl;
cout << "NY" << endl;
cout << "YN" << endl;
exit( 0 );
}
queue< int > que;
for( int i = 2; i < MAXN; ++i ){
que.emplace( i );
}
int f = 0;
for( int i = 31 - __builtin_clz( K ) - 1, len = 2 ; i >= 0; len += 2, --i ){
int u = que.front(); que.pop();
int d = que.front(); que.pop();
int m = 1; if( i > 0 ) m = que.front(), que.pop();
G[ f ][ u ] = G[ u ][ f ] = 1;
G[ f ][ d ] = G[ d ][ f ] = 1;
G[ u ][ m ] = G[ m ][ u ] = 1;
G[ d ][ m ] = G[ m ][ d ] = 1;
f = m;
if( K >> i & 1 ){
int p = 0;
for( int j = 0; j < len - 1; ++j ){
int nxt = que.front(); que.pop();
G[ p ][ nxt ] = G[ nxt ][ p ] = 1;
p = nxt;
}
G[ p ][ f ] = G[ f ][ p ] = 1;
}
}
cout << MAXN << endl;
for( int i = 0; i < MAXN; ++i ){
for( int j = 0; j < MAXN; ++j ){
cout << "NY"[ G[ i ][ j ] ];
}
cout << "\n";
}
return 0;
}
```