import random, math, time


class Grid(object):
    def __init__(self, n):
        self.n = n
        self.a = [[0]*n for _ in range(n)]
        self.filled = 0

    def __str__(self):
        return "\n".join("".join(str(c) for c in r) for r in self.a)

    def on(self, i, j):
        if not self.a[i][j]: self.filled += 1
        self.a[i][j] = 1

    def off(self, i, j):
        if self.a[i][j]: self.filled -= 1
        self.a[i][j] = 0

    def get_rand_ind(self):
        return (random.randint(0, self.n-1),random.randint(0, self.n-1))


    def check_squares(self, i, j):
        for d in range(-i, self.n-i):
            if d==0: continue
            for sgn in [-1, 1]:
                #if any(t<0 or t>=self.n for t in (i+d, j+sgn*d)): continue
                y1 = j+sgn*d
                if y1<0 or y1>=self.n: continue
                crns = [(i+d, j), (i+d, y1), (i, y1)]
                if all(self.a[x][y] for x,y in crns):
                    #print ("corners ", crns, " form square")
                    return True
        return False



    def sim_an(self, kMax=10**6):
        T = 1.0
        k = 0

        bestFilled = self.filled
        bestGrid = str(self)
        startT = time.time()
        while k<kMax:
            T = 1.0 - float(k)/kMax
            i,j = self.get_rand_ind()
            if self.a[i][j]:
                if random.random()<math.exp(-1.0/T):
                    self.off(i,j)
            else:
                if not self.check_squares(i,j):
                    self.on(i,j)
            if self.filled>bestFilled:
                bestFilled = self.filled
                bestGrid = str(self)
                print ("New Best: %d" %bestFilled)
                print ("T = %f" %T, "k = %d" %k)
                #print (bestGrid)
            k += 1

        print ("Simulated annealing over.")
        print ("Time: %f" %(time.time()-startT))
        print ("Best found: %d" %bestFilled)
        print (bestGrid)

    #for testing
    def print_possibs(self):
        ret = ""
        for i in range(self.n):
            for j in range(self.n):
                ret += "x" if self.check_squares(i,j) else "*"
            if i==self.n-1: break
            ret += "\n"
        print (ret)



testN = 100
g = Grid(testN)

g.sim_an(kMax = 10**8)



##########################################
#----TULOKSET------#######################
##########################################

"""
n = 10

Simulated annealing with kMax=10e7 over.
Time: 337.874000
Best found: 60
0111111001
0101010011
1110011101
1001100111
1101001001
1011101110
1100101011
0100110101
1010010111
1111010010

"""

"""
n=20

Simulated annealing with kMax=10e8 over.
Time: 4828.471000
Best found: 203
10000011101010011101
00001101011011110110
11100111010110011000
01010010111101001000
01011110100001101011
11101011000000011110
10111001100001100101
01010101010100100110
00110111011000001011
11100100000100011101
00101010011110010101
11011000001011010011
10110000001101111010
11101000111000101111
00110101101110000101
10000111011010100011
11110001110110100001
01011110010011010100
11000100101101110110
00010011010101001101

"""




"""
n=100

Simulated annealing with kMax=10e8 over.
Time: 16381.919000
Best found: 3243

0100000000000001000010100101011011000110101100100010110001011110000000000000001110100011100100100101
0000100000111000010110100011010010000010010001011000011010110010001000110011100011100101010000001000
1110100001001001001011000100101100010001001000010001110111000000000100010010110000111101100001010010
0101100101100010010010001000110001110011100010100011001000101010000001010010000010010100000110010011
1000111101010111100011001010000111001001010010010001001001011000001110000101001001000010000001001100
0011010000100100001010000000111010001000101001011101011001001100011000011000010011011010010011100000
1001001000110001000011110010000011111000100110000010001101001010100100000100000100000111101001011000
0111000000100101011100000011100100001010100100110000000010101101000010110100000101001000100010000000
0100100010001101000000101000100110000000000110101110000110011001010100001111010000001011001010011111
1010001110100100000000111100001010100011010001101010001100100000110000011001101000001110000001010101
1100110010000100010111010101000000101010010000100110110001010100100110101000100001110000101100010000
0011100110000101100000001110111000110010001101000100101001010101000000011110001000000111010000110001
0100110001001010001000110011000001000101100101000101011001100010101001000001100000001100110010000001
0001011000011000010101100001001111001011000001001111000010000000100010000000110010111010011100001000
0110000010110000100000001100010010001110001000011000001010010000100001010101010000101101110110000101
0010100001010100000001110101100001110001000000010010010100100101000011100100011010010001000000000010
0100001110011000001000011100100000010000110111010000010000100000101010000110000010100000000111011100
0111010101001000100101101010000000010000001101111011000000000110001100000011000010000100011100100010
1001110100110000100100001000101001001100101010100000001000010000011000001010001000110000010011001001
1011001100000010010000110110010100000100100000000011110000001000100010101000010000000001101101100100
0100000000100010010010011100001001010010000000111000000010110100100101001100100001000010101011000000
0011111010000000100000000001001010100000011011000010000010001000001111001010011101100110100000001000
0000010100000111001101110000010000100000001000001101110100110010000001001001001000000001000010010010
1000100110111001000110000000011000111000000011100010000000000011001001010011001001100001000011100010
1010000000000000011000001101100000000100101000001000111001111010000000100100011100001000110000110110
0001101101000110000011001010000000100000001011000000101011000010000001000010100100000010100010000010
0110010000101010000100100000001100010100011000100010100010010000100100100000000110001110101000011000
1100010110100010000010010000100000000001100001001111100101000011000011100001001001000010011000010101
0111110001000010011011000001000000000000010001000100000011101001001000000000000000000010001110111101
1001000010000100000000100000100000011100100010000001000000010101001010000000100101000110000100000110
1011000011111100011000000000000000000110001101000111010010001000001000000000100001000001110111001011
0100000000100101100000010101000101000000010010001010010100100001100000000001111000010100000001110000
0010101110001000010010000010000000100111010110000000010000100100000000011000000101101001100010100101
0001001010001001101010000000000100000100101100000000101100000001001010101000110000001010111001000001
0000110011100000111001000000011010100100000010001100001010010001001000000000001010001000001111010011
0110010100011001000010000000010100000000010000010000000101010100110000000110000110010001011000010001
1100101000001000100011000010100001000001000010000000111000011101010100010001101101000100000001000010
1001011001010100010000000000000010001100000000000000101100000100000001010100100110000000010100110100
0100000001011010100101001010011001000110010000100011110000000000000010010010010000010000011011010110
1000000000010000111110011101010000000000000100001000010010000001000011101000000010010100000010111010
0000000000000010010010110111111001001111111010001000000100000001000001000010100000000000011100000110
0101100010100001000100000001001000010000000000000001001001100010100100100000011011111000001000001101
0100010010010100001100100001100001100000000000000100110000000000001000010110001000101001111000011000
1011110110001010100000000000000000000000000000010000000000111110001011010100000010011101001000101100
1101000000101111101000000000010100000001010000100000000000001001001000100111001100100100011100000100
0100001010000100110101001000100100100001100000001000000010000011000000000000001000000100100111010101
1100001110010110000000111001000000000010000000000000100000000000010101001010000101110100010000111001
0100000001000100000100001100010110110101100001000001000000100000010000100000010010000110110110101001
0000101001001101000000011011101010010101011000000000000000000000010000000000010000110001000100011110
0111110100110100100100101100000001000000000000000000000000001000000110011011010011000111000110000001
0010001000010100010000101000011001101000001010000100000000000100100100000000001000101001010001000111
1010001100100011011110010000000000001000000010000010000000000000000001011000110111101110100000001101
0001011010100001100001011100000001001001000100100000000000000010111011001100101010100010000001101000
0001010001110000101101010000000100100010001010001000000000000000010000100101100010000100100010011100
1010110000011110000001001101010000000000000110100000000000000000010100110110100000000001110100100011
1011000100110001001010111000000000011000000000010000100001000000010100001100000010100000001011100101
0010011001010010101000100000100001100000001100000000000100000000000100111000000000000010101100101110
0000101111101010110000100110000100100000000000000001000000000101000000000011111000001011101000110011
0111010001001010000110101101000110101000010000000000001000000011010000000101000101001000001110011001
0000001100100000000011010110100011001000110000011111000011000100000100000000000010011000000000010110
1000111010001000001010000010000000000001010100010100000100010110010010001011000000110000010011100000
1111000011000000000111000100101010100000000100000000000000000000010110000001010101000100111001010010
1010000000001000100101001000000011010110000001000010001001001000000100011101110001001001000000001100
1001110001000001001000000001110101000000010000111000100010100010000000100011000001000001100011001011
0100010001101100001110101000010100010001000000000100001000000100000011000000101101010000010100001010
1100001100000001101000101111100000010100001010010000000100000011101000010000100101010000000100110101
0101100100011001000100010010100000010001000000101100001000000000010110001000010100001001101000100100
1100000000000000001001010110010100000001000000100100000000000000110101110001001100000010000010110001
0001000101111011110001000011000000001100000000010000000000001010000010100000010000011010011011001001
0110000110010010100100000001000110111000000100011001011000010010000001101001011100000000110001100000
1000111010010100100010000000001000100110010000110000000001011100010101000100001000011000000110000100
1001000110000000000000000011000101011011100001010000000100001010110010001110000100100001000000100110
0011001001110000100000000000000010000110110000100100000001001010100000101000001110011101010010100010
1101001110000110010000000000100100000010001000111100110001010000001001100000000010100111101001000001
1000001000010100000000101100110101110000000100010110000111010000000011000010000010000000100110001010
0010110001011111011000000000000000100000100101011010100001000100110000000010000010001000001101011011
1100000000001000100000010110100010100011000000000000001000110111101010001000001010010000111010010000
1010001000100010110100010000001110000000101100010000001011100100000000000010100101100100000011000110
0000101001000011100011111001011000000000000110100100011110000000000000000100110110011000000000101100
1000010100111010000000100001001001001011110100101001000000010000110010100000001011100000001100100111
0000011101010000001100000100000010100001000001111000000110001001001101110010100000010000111000001010
1001000100001001010001110010001010110000000000000110110100011010000011000011011101101010000100000000
1101010010110000000000101000111100011110101010000000011000010010110000010000110000111100001001000000
0000101010010110011001000001000110010010101001100001000100100001000101001010000010100011000010010101
1100000011011010010001000000000101111001000001011000000100100000100000000110100000000010111011100100
0000000100000011011110001000010010101100000001010001111100100110001010000100000000001110101000100100
0000001101000001001010001100001010000110100101001100101010010011011000110110000001100101110000100010
0010110001000000101101010001000010010010010110011010001000100110110001010100010000000100100001110000
1000001001100011000110010011000001100001111100000001000110001100101100000000110000000011000100101010
1010011010000100011011000100010011010001010001100000000011100100100100000101001111000000100000101011
0000010001101110101000001101101010100000100010100100101000100001010100010100101001010011100101000101
0010111000101001000101001011011000101100110010100101100011000000111010000100000100100110110000001101
0010000111000100000011101110010001100111011000000110110110000001000001010000011010100011000001001000
0111000001110000000010000010001100000010110100100001011100100000000110111100000100001000000010011110
1000000011001010000100110100110001101010001110110000100111100001101000000100010000111010000110101000
0000100010100000011010000000001110011010001000001010101001010000011111001001100000010110001000001001
0001011101011000010010010010000100000010000111000010011110010101010101000001010100000101101000010001
0001010001110011001000100010010100011001011100000110010000101100100100100010011010011001001001010100
0000100001001101001001010110000000001001001001011011111000001010100110010001101010010100100001100010
1110001100010100111101100010001000000000011011101001010001001010101001110011000011110110000000001001

"""