Problem:


Score : 800 points

Problem Statement

Takahashi is doing a research on sets of points in a plane.
Takahashi thinks a set S of points in a coordinate plane is a good set when S satisfies both of the following conditions:

The distance between any two points in S is not \sqrt{D_1}.

The distance between any two points in S is not \sqrt{D_2}.

Here, D_1 and D_2 are positive integer constants that Takahashi specified.

Let X be a set of points (i,j) on a coordinate plane where i and j are integers and satisfy 0 ≤ i,j < 2N.

Takahashi has proved that, for any choice of D_1 and D_2, there exists a way to choose N^2 points from X so that the chosen points form a good set.
However, he does not know the specific way to choose such points to form a good set.
Find a subset of X whose size is N^2 that forms a good set.

Constraints

1 ≤ N ≤ 300

1 ≤ D_1 ≤ 2×10^5

1 ≤ D_2 ≤ 2×10^5

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N D_1 D_2

Output

Print N^2 distinct points that satisfy the condition in the following format:

x_1 y_1
x_2 y_2
:
x_{N^2} y_{N^2}

Here, (x_i,y_i) represents the i-th chosen point.
0 ≤ x_i,y_i < 2N must hold, and they must be integers.
The chosen points may be printed in any order.
In case there are multiple possible solutions, you can output any.

Sample Input 1

2 1 2

Sample Output 1

0 0
0 2
2 0
2 2

Among these points, the distance between 2 points is either 2 or 2\sqrt{2}, thus it satisfies the condition.

Sample Input 2

3 1 5

Sample Output 2

0 0
0 2
0 4
1 1
1 3
1 5
2 0
2 2
2 4



Sample input:
2 1 2


Sample output:
0 0
0 2
2 0
2 2

Submission status: Wrong Answer

Solution code:

def circle(D):
    T = int(D**0.5)+1
    temp = []
    for i in range(0,D+1):
        if D-i*i < 0 or ((D-i*i)**0.5)%1:
            pass
        else:
            XX = int((D-i*i)**0.5)
            temp.append((XX,i))
            temp.append((XX,-i))
            temp.append((-XX,i))
            temp.append((-XX,-i))
    return list(set(temp))

def main():

    n = list(map(int,input().split()))

    N = n[0]
    D1 = n[1]
    D2 = n[2]

    map1 = circle(D1)
    map2 = circle(D2)

    mapp = [[0 for x in range(0,2*N)] for y in range(0,2*N)]
    count = 0
    mem = []
    for i in range(0,2*N):
        for j in range(0,2*N):
            if mapp[i][j] == 0:
                count += 1
                mapp[i][j] = 2 
                mem.append([i,j])
                for k in map1:
                    if i + k[0] > -1 and j+k[1] > -1 and j+k[1] < 2 * N and i+k[0] < 2 * N:
                        mapp[i+k[0]][j+k[1]]=1
                    else:
                        pass
                for k in map2:
                    if i + k[0] > -1 and j+k[1] > -1 and j+k[1] < 2 * N and i+k[0] < 2 * N:
                        mapp[i+k[0]][j+k[1]]=1
                    else:
                        pass
            else:
                pass
            if count >= N*N:
                break
        if count >= N*N:
            break


    for i in mem:
        print(i[0],i[1])

main()

"""
from scipy.special import perm, comb

def C(x,y,dic,com):
    if y==0 or x == y:
        return 1
    elif (x,y) in dic.keys():
        return dic[(x,y)]
    else:
        dic[(x,y)] = comb(x,y,exact=True)#(C(x-1,y-1,dic,com)+C(x-1,y,dic,com))
        return dic[(x,y)]

def main():
    MAX =  998244353
    n = list(map(int,input().split()))
    N = n[0]
    A = n[1]
    B = n[2]
    K = n[3]

    r = A
    g = A+B
    b = B

    point = []

    X = -1
    while(K - X * r > -1 ):
        X = X + 1
        if ((K-X * r) % (b)):
            continue
        else:
            point.append((X,int((K-X * r) / (b))))
            continue
    dic2 = []
    for i in point:
        x = i[0]
        y = 0
        z = i[1]
        while((x > -1)and(z > -1)):
            if (x + y + z) > N:
                pass
            else:
                dic2.append([x+y+z,x,y,z])
            x = x -1
            z = z -1
            y = y +1
    dic2.sort()
    print(dic2)
    count = 0
    dict = {}

    for i in dic2:
        x = i[1]
        y = i[2]
        z = i[3]
        count = (count + C(N,x,dict,comb)*C(N-x,y,dict,comb)*C(N-(x+y),z,dict,comb))%MAX
        
    print(count)
main()
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n, d1, d2 = map(int,input().split())

if d1 % 4 !=0 and d2 % 4 !=0:
    for i in range(n):
        for j in range(n):
            print(2*i, 2*j)

if d1%4 !=0 and d2 %4 == 0:
    d1,d2=d2,d1

if d1 % 4 == 0 and d2 % 4 == 0:
    c=0
    i=0;j=0;
    while c < n*n:
        print(i,j)
        c+=1
        if i + 3 < 2*n:
            i +=3
        else:
            j+=1
            i = (i%3+1)%3

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n, d1, d2 = map(int,input().split())

if d1 % 4 !=0 and d2 % 4 !=0:
    for i in range(n):
        for j in range(n):
            print(2*i, 2*j)

if d1%4 !=0 and d2 %4 == 0:
    d1,d2=d2,d1

if d1 % 4 == 0 and d2 % 4 == 0:
    c=0
    i=0;j=0;
    while c < n*n:
        print(i,j)
        if i + 3 < 2*n:
            i +=3
        else:
            j+=1
            i = (i%3+1)%3

Submission status: Wrong Answer

Solution code:
def circle(D):
    T = int(D**0.5)+1
    temp = []
    for i in range(0,D+1):
        if D-i*i < 0 or ((D-i*i)**0.5)%1:
            pass
        else:
            XX = int((D-i*i)**0.5)
            temp.append((XX,i))
            temp.append((XX,-i))
            temp.append((-XX,i))
            temp.append((-XX,-i))
    return list(set(temp))

n = list(map(int,input().split()))

N = n[0]
D1 = n[1]
D2 = n[2]

map1 = circle(D1)
map2 = circle(D2)


mapp = [[0 for x in range(0,2*N)] for y in range(0,2*N)]

count = 0
mem = []
for i in range(0,2*N):
    for j in range(0,2*N):
        if mapp[i][j] == 0:
            count += 1
            mapp[i][j] = 2 
            mem.append([i,j])
            for k in map1:
                if i + k[0] > -1 and j+k[1] > -1 and j+k[1] < 2 * N and i+k[0] < 2 * N:
                    mapp[i+k[0]][j+k[1]]=1
                else:
                    pass
            for k in map2:
                if i + k[0] > -1 and j+k[1] > -1 and j+k[1] < 2 * N and i+k[0] < 2 * N:
                    mapp[i+k[0]][j+k[1]]=1
                else:
                    pass
        else:
            pass
        if count >= N*N:
            break
    if count >= N*N:
        break


for i in mem:
    print(i[0],i[1])

Submission status: Wrong Answer

Solution code:
from math import sqrt

N0,D1,D2 = map(int,input().split())
N = 2*N0
banned = set()
for d in [D1,D2]:
  for x in range(0, int(sqrt(d/2))+2):
    if d > x*x:
      y = sqrt(d-x*x)
      if y == int(y):
        y = int(y)
        banned.add((x,y))
        banned.add((y,x))

grid = [[True for _ in range(N)] for _ in range(N)]

points = []

for y in range(N):
  for x in range(N):
    if grid[y][x]:
      points.append((x,y))

      for dx,dy in banned:
        if x+dx < N and y+dy < N:
          grid[y+dy][x+dx] = False

# from time import sleep

# print(len(points),N0**2)
# import numpy as np
# print(np.array(grid, dtype=int))

for x,y in points[:N0**2]:
  print(x,y)

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N

if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
else:
 for i in range(2*N):
  tt = i * i
  if C - tt in check or D - tt in check:
   continue
  else:
   for j in range(2*N):
    print(i,j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break

Submission status: Wrong Answer

Solution code:
import numpy as np
N, D1, D2 = map(int, input().split())
points = []
print_count = 0
i = 0
j = 0
while(True):
    flag = 1
    for p in points:
        D = int((i-p[0])**2 + (j-p[1])**2)
        if ((D == D1) | (D == D2)):
            flag *= 0
    if flag:
        print(str(i) + " " + str(j))
        print_count += 1
        points.append([i, j])
    if (print_count == N*N):
        break
    i += 1
    if (i > 300):
        i = 0
        j += 1

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N
 
print(check)
if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
else:
 for i in range(2*N):
  tt = i * i
  if C - tt in check or D - tt in check:
   continue
  else:
   for j in range(2*N):
    print(i,j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    def seek_size():
        x, y = 0, 0
        ddmin = float('inf')
        for i1 in xrange(3):
            for i2 in xrange(3):
                if i1 == i2 == 0: continue
                dd = i1**2 + i2**2
                if d1 == dd or d2 == dd: continue
                if d1 % dd == 0: continue
                if d2 % dd == 0: continue
                if dd < ddmin:
                    ddmin = dd
                    x, y = i1, i2
        return x, y

    x, y = seek_size()
    ans = []
    for xx in xrange(-10*n, 10*n):
        for yy in xrange(-10*n, 10*n):
            xi = xx*x + yy*y
            yi = xx*y - yy*x
            if 0 <= xi < 2*n and 0 <= yi < 2*n:
                ans.append((xi, yi))
            if len(ans) == n**2: break
        if len(ans) == n**2: break
    if len(ans) != n**2:
        for i in ans:
            if 0 <= i[0]+1 < 2*n:
                ans.append((i[0]+1, i[1]))
            if len(ans) == n**2: break
    if len(ans) != n**2: raise RuntimeError

    return "\n".join(["%d %d"%item for item in ans])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N+1)]
time = 0
stop = N * N
 
print(check)
if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
else:
 for i in range(2*N):
  tt = i * i
  if C - tt in check or D - tt in check:
   continue
  for j in range(2*N):
   print(i,j)
   time += 1
   if stop == time:
    break
  if stop == time:
   break

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    def seek_size():
        x, y = 0, 0
        ddmin = float('inf')
        for i1 in xrange(3):
            for i2 in xrange(3):
                if i1 == i2 == 0: continue
                dd = i1**2 + i2**2
                if d1 == dd or d2 == dd: continue
                if d1 % dd == 0: continue
                if d2 % dd == 0: continue
                if dd < ddmin:
                    ddmin = dd
                    x, y = i1, i2
        return x, y

    x, y = seek_size()
    ans = []
    for xx in xrange(-10*n, 10*n):
        for yy in xrange(-10*n, 10*n):
            xi = xx*x + yy*y
            yi = xx*y - yy*x
            if 0 <= xi < 2*n and 0 <= yi < 2*n:
                ans.append((xi, yi))
            if len(ans) == n**2: break
        if len(ans) == n**2: break
    if len(ans) != n**2:
        for i in ans:
            ans.append((i[0]+1, i[1]))
            if len(ans) == n**2: break
    if len(ans) != n**2: raise RuntimeError

    return "\n".join(["%d %d"%item for item in ans])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
from math import sqrt

N0,D1,D2 = map(int,input().split())
N = 2*N0
banned = set()
for d in [D1,D2]:
  for x in range(0, int(sqrt(d/2)+1)):
    y = sqrt(d-x*x)
    if y == int(y):
      y = int(y)
      banned.add((x,y))
      banned.add((y,x))

grid = [[True for _ in range(N)] for _ in range(N)]

points = []

for y in range(N):
  g = grid[y]
  for x in range(N):

    if g[x]:
      points.append((x,y))

      for dx,dy in banned:
        if x+dx < N and y+dy < N:
          grid[y+dy][x+dx] = False

from time import sleep

if len(points) < N0**2:
  sleep(3)

for x,y in points[:N0**2]:
  print(x,y)

Submission status: Wrong Answer

Solution code:
N, D1, D2 = map(int, input().split())

for i in range(N):
    for j in range(N):
        print(str(2*i)+" "+ str(2*j))

Submission status: Wrong Answer

Solution code:
from math import sqrt

N0,D1,D2 = map(int,input().split())
N = 2*N0
banned = set()
for d in [D1,D2]:
  for x in range(0, int(sqrt(d/2)+1)):
    y = sqrt(d-x*x)
    if y == int(y):
      y = int(y)
      banned.add((x,y))
      banned.add((y,x))

grid = [[True for _ in range(N*2)] for _ in range(N*2)]

points = []

for y in range(N):
  g = grid[y]
  for x in range(N):

    if g[x]:
      points.append((x,y))

      for dx,dy in banned:
        if x+dx < N and y+dy < N:
          grid[y+dy][x+dx] = False

from time import sleep

if len(points) < 100:
  sleep(3)

for x,y in points[:N0**2]:
  print(x,y)

Submission status: Wrong Answer

Solution code:
from math import sqrt

N0,D1,D2 = map(int,input().split())
N = 2*N0
banned = set()
for d in [D1,D2]:
  for x in range(0, int(sqrt(d/2)+1)):
    y = sqrt(d-x*x)
    if y == int(y):
      y = int(y)
      banned.add((x,y))
      banned.add((y,x))

grid = [[True for _ in range(N*2)] for _ in range(N*2)]

points = []

for y in range(N):
  g = grid[y]
  for x in range(N):

    if g[x]:
      points.append((x,y))

      for dx,dy in banned:
        if x+dx < N and y+dy < N:
          grid[y+dy][x+dx] = False

for x,y in points[:N0**2]:
  print(x,y)

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N

if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
else:
 for i in range(2*N):
  tt = i * i
  if C - tt in check or D - tt in check:
   continue
  for j in range(2*N):
   print(i,j)
   time += 1
   if stop == time:
    break
  if stop == time:
   break

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N

if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
else:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    if C % 2 == 1:
     if D - j * j not in check:
      print(i, j)
      time += 1
      if stop == time:
       break
    else:
     if C - j * j not in check:
      print(i, j)
      time += 1
      if stop == time:
       break
   if stop == time:
    break

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N

if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break

Submission status: Wrong Answer

Solution code:
N, C, D = map(int, input().split())
check = [i*i for i in range(N)]
time = 0
stop = N * N

if C * D % 2 ==1:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
elif (C+D) % 2 == 0:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 1:
    print(i, j)
    time += 1
    if stop == time:
     break
  if stop == time:
   break
else:
 for i in range(2*N):
  for j in range(2*N):
   if (i + j) % 2 == 0:
    if C % 2 == 1:
     if D - j * j not in check:
      print(i, j)
      time += 1
      if stop == time:
       break
    else:
     if C - j * j not in check:
      print(i, j)
      time += 1
      if stop == time:
       break
   if (i + j) % 2 == 1:
    if C % 2 == 1:
     if C - j * j not in check:
      print(i, j)
      time += 1
      if stop == time:
       break
    else:
     if D - j * j not in check:
      print(i, j)
      time += 1
      if stop == time:
       break

   if stop == time:
    break

Submission status: Wrong Answer

Solution code:
N, D1, D2 = [int(x) for x in raw_input().split()]
bads = set()
for D in (D1, D2):
    for i in range(2 * N):
        if i * i > D:
            break
        j = int((D - i * i) ** 0.5)
        if i * i + j * j != D or j >= 2 * N:
            continue
        bads.add(i + j * 1j)
        bads.add(i - j * 1j)
        bads.add(-i + j * 1j)
        bads.add(-i - j * 1j)

cur_bads = bads.copy()

remaining = N * N

for i in range(2 * N):
    for j in range(2 * N):
        p = i + j * 1j
        if (i + j * 1j) not in cur_bads:
            print i, j
            remaining -= 1
            if remaining == 0:
                import sys
                sys.exit(0)
            cur_bads |= {x + p for x in bads}

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def gcd(a, b):
    """greatest common divisor"""
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


def solve(f):
    n, d1, d2 = f.read_int_list()

    def seek_size():
        x, y = 0, 0
        ddmin = float('inf')
        for i1 in xrange(5):
            for i2 in xrange(5):
                if i1 == i2 == 0: continue
                dd = i1**2 + i2**2
                if dd != d1 and dd != d2 and d1 % dd != 0 and d2 % dd != 0:
                    if dd < ddmin:
                        ddmin = dd
                        x, y = i1, i2
        return x, y

    x, y = seek_size()
    ans = []
    for xx in xrange(-5*n, 5*n):
        for yy in xrange(-5*n, 5*n):
            xi = xx*x + yy*y
            yi = xx*y - yy*x
            if 0 <= xi < 2*n and 0 <= yi < 2*n:
                ans.append("%d %d"%(xi, yi))
            if len(ans) == n**2: break
        if len(ans) == n**2: break

    return "\n".join(ans)


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,d1,d2 = LI()
    nn = n**2
    n2 = n*2
    r = []
    t = []
    for i in range(n*2):
        ii = i**2
        for j in range(i, n*2):
            jj = j**2
            if ii+jj == d1 or ii+jj == d2:
                t.append((i,j))
                t.append((i,-j))
                t.append((-i,j))
                t.append((-i,-j))
                if i != j:
                    t.append((j,i))
                    t.append((j,-i))
                    t.append((-j,i))
                    t.append((-j,-i))
    f = [[None] * (n*2) for _ in range(n*2)]
    t = list(set(t))
    for i in range(n*2):
        for j in range(n*2):
            if not f[i][j] is None:
                continue
            f[i][j] = 1
            r.append((i,j))
            if len(r) == nn:
                break
            for di,dj in t:
                ni = i + di
                nj = j + dj
                if 0 <= ni < n2 and 0 <= nj < n2:
                    f[ni][nj] = 1

        if len(r) == nn:
            break

    return '\n'.join(map(lambda x: '{} {}'.format(x[0],x[1]), r))


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,d1,d2 = LI()
    nn = n**2
    n2 = n*2
    r = []
    t = []
    for i in range(n*2):
        ii = i**2
        for j in range(i, n*2):
            jj = j**2
            if ii+jj == d1 or ii+jj == d2:
                t.append((i,j))
                t.append((i,-j))
                if i != j:
                    t.append((j,i))
                    t.append((j,-i))
    f = [[None] * (n*2) for _ in range(n*2)]
    for i in range(n*2):
        for j in range(n*2):
            if not f[i][j] is None:
                continue
            f[i][j] = 1
            r.append((i,j))
            if len(r) == nn:
                break
            for di,dj in t:
                ni = i + di
                nj = j + dj
                if 0 <= ni < n2 and 0 <= nj < n2:
                    f[ni][nj] = 1

        if len(r) == nn:
            break

    return '\n'.join(map(lambda x: '{} {}'.format(x[0],x[1]), r))


print(main())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, D1, D2 = map(int, raw_input().split())

anss = []
for D in [D1, D2]:
    ls = []
    for i in range(600):
        for j in range(600):
            if i * i + j * j == D:
                ls += [(i, j), (i, -j), (-i, j), (-i, -j)]
    
    ls = list(set(ls))

    ans = [[0] * 2 * N for i in range(2 * N)]

    def func(x, y, c):
        if x < 0 or y < 0 or x >= 2 * N or y >= 2 * N:
            return
        if ans[y][x] != 0:
            return
        ans[y][x] = c
        c = '.' if c == '#' else '#'
        for dx, dy in ls:
            func(x + dx, y + dy, c)

    for i in range(2 * N):
        for j in range(2 * N):
            if ans[i][j] == 0:
                func(j, i, '#')
    anss.append(ans)

ans1, ans2 = anss

m_ls = {'..': [], '.#': [], '#.': [], '##': []}

for i in range(2 * N):
    for j in range(2 * N):
        s = ans1[i][j] + ans2[i][j]
        m_ls[s] += [(i, j)]

for s in m_ls:
    if len(m_ls[s]) >= N * N:
        ls = m_ls[s]
        for i in range(N * N):
            print ls[i][0], ls[i][1]
        exit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, D1, D2 = map(int, raw_input().split())

ls1 = []
ls2 = []

for i in range(600):
    for j in range(600):
        if i * i + j * j == D1:
            ls1 += [(i, j), (i, -j), (-i, j), (-i, -j)]
        if i * i + j * j == D2:
            ls2 += [(i, j), (i, -j), (-i, j), (-i, -j)]

ls1 = list(set(ls1))
ls2 = list(set(ls2))

ans1 = [[0] * 2 * N for i in range(2 * N)]
ans2 = [[0] * 2 * N for i in range(2 * N)]

def func(x, y, c, ans, ls):
    if x < 0 or y < 0 or x >= 2 * N or y >= 2 * N:
        return
    if ans[y][x] != 0:
        return
    ans[y][x] = c
    c = '.' if c == '#' else '#'
    for dx, dy in ls:
        func(x + dx, y + dy, c, ans, ls)

for i in range(2 * N):
    for j in range(2 * N):
        if ans1[i][j] == 0:
            func(j, i, '#', ans1, ls1)
        if ans2[i][j] == 0:
            func(j, i, '#', ans2, ls2)

m_ls = {'..': [], '.#': [], '#.': [], '##': []}

for i in range(2 * N):
    for j in range(2 * N):
        s = ans1[i][j] + ans2[i][j]
        m_ls[s] += [(i, j)]

for s in m_ls:
    if len(m_ls[s]) >= N * N:
        ls = m_ls[s]
        for i in range(N * N):
            print ls[i][0], ls[i][1]
        exit()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

N, D1, D2 = map(int, raw_input().split())

Ds = [D1]

ls1 = []
ls2 = []

for i in range(600):
    for j in range(600):
        if i * i + j * j == D1:
            ls1 += [(i, j), (i, -j), (-i, j), (-i, -j)]
        if i * i + j * j == D2:
            ls2 += [(i, j), (i, -j), (-i, j), (-i, -j)]

ls1 = list(set(ls1))
ls2 = list(set(ls2))

ans1 = [[0] * 2 * N for i in range(2 * N)]
ans2 = [[0] * 2 * N for i in range(2 * N)]

def func(x, y, c, ans, ls):
    if x < 0 or y < 0 or x >= 2 * N or y >= 2 * N:
        return
    if ans[y][x] != 0:
        return
    ans[y][x] = c
    c = '.' if c == '#' else '#'
    for dx, dy in ls:
        func(x + dx, y + dy, c, ans, ls)

for i in range(2 * N):
    for j in range(2 * N):
        if ans1[i][j] == 0:
            func(j, i, '#', ans1, ls1)
        if ans2[i][j] == 0:
            func(j, i, '#', ans2, ls2)

m_ls = {'..': [], '.#': [], '#.': [], '##': []}

for i in range(2 * N):
    for j in range(2 * N):
        s = ans1[i][j] + ans2[i][j]
        m_ls[s] += [(i, j)]

for s in m_ls:
    if len(m_ls[s]) >= N * N:
        ls = m_ls[s]
        for i in range(N * N):
            print ls[i][0], ls[i][1]
        exit()