CROSSBIT - Crossbits

Crossbits are like Crosswords; instead of entering words you enter binary bits 01 in a Crossbit under certain given conditions, assuming that a solution exists. An empty Crossbit of size N is an empty grid of size N×N.

Given a natural number N , consider entering N2 binary bits in an empty Crossbit, satisfying the following conditions:

  • Each square in the grid contains either a 0-bit or a 1-bit with no 1-bit in two major diagonals.
  • The total number of 1-bit in each row / column is exactly equal to K , K being a given natural number less than N.
  • A 0-bit has at least another adjacent 0-bit either in the same row or in the same column.
  • The Crossbit represents the N2 -bit binary number B formed by placing bits in the 1st , the 2nd , ... the Nth row from left to right.

You are required to write a program that enters bits in an empty Crossbit so that the Crossbit represents the least binary number B for given N and K .

As an illustration consider the case with N = 4 and K = 1 . The Crossbit shown below represents the least binary number B = 0010100000010100 of 16 bits satisfying the specified conditions.

0 	0 	1 	0
1 	0 	0 	0
0 	0 	0 	1
0 	1 	0 	0

Input

The input may contain multiple test cases.

For each test case parameters N and K of the Crossbit are given in one line. Assume that N does not exceed 10.

The input terminates with a line containing 0 as input.

Output

For each test case, print the Crossbit in N rows; each row contains N bits with a space between two neighbouring bits. Keep a blank line after the last output line of each test case.

Example

Sample Input
4 1
6 2
0

Sample Output
0 0 1 0 
1 0 0 0 
0 0 0 1 
0 1 0 0 

0 0 0 1 1 0 
1 0 0 1 0 0 
0 0 0 0 1 1 
1 1 0 0 0 0 
0 0 1 0 0 1 
0 1 1 0 0 0

Added by:Jimmy
Date:2008-12-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2006

hide comments
2015-04-09 00:24:53 Lucas Melo
0 can be considered a natural number too.
2015-04-07 16:38:54 Aleksa
Problem statement is not correct. K can have value of zero. In text, it is clearly written that k is natural number, thus greater than zero. It took me 16 submissions to solve this!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.