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:
N, D1, D2 = map(int, input().split())
r1, r2 = D1 % 8, D2 % 8
RL = [[3, 3], [3, 6], [3, 7], [6, 3], [6, 6], [6, 7], [7, 3], [7, 6], [7, 7]]
if [r1, r2] in RL:
  for i in range(N*N):
    print(i % N, (i // N) % N)
else:
  if D1 % 4 != 0 and D2 % 4 != 0:
    for i in range(N):
      for j in range(N):
        print(2*i, 2*j)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

N,*D = map(int,input().split())

grid = np.zeros((2*N,2*N), dtype=np.int8)

for i,d in enumerate(D):
    width = 1
    while d % 4 == 0:
        d //= 4
        width *= 2
    if d == 1:
        x = np.arange(2*N)
        bl = (x%(2*width) >= width)
        grid += (bl[:,None]^bl[None,:]) * (1<<i)
    elif d == 2:
        x = np.arange(2*N)
        bl = (x%(2*width) >= width)
        grid += bl * (1<<i)

for i in range(4):
    X,Y = np.where(grid == i)
    if len(X) >= N*N:
        break

X,Y = X[:N*N], Y[:N*N]
for x,y in zip(X,Y):
    print(x,y)

Submission status: Wrong Answer

Solution code:
N, D1, D2 = map(int, input().split())
for i in range(N**2):
    print(0, 0)

Submission status: Wrong Answer

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(500):
        for j in range(500):
            if i * i + j * j == D:
                ls += [(i, j), (i, -j), (-i, j), (-i, -j)]
    
    ls = list(set(ls))

    ans = [[-1] * 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] != -1:
            return
        ans[y][x] = c
        c = not c
        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] == -1:
                func(j, i, True)
    anss.append(ans)

ans1, ans2 = anss

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

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

Submission status: Wrong Answer

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)]
        if i * i + j * j == D2:
            ls2 += [(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: Wrong Answer

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)]
        if i * i + j * j == D2:
            ls2 += [(i, j)]

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: Wrong Answer

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

import numpy as np
n, d1, d2 = map(int, input().split())

table = np.zeros((2 * n, 2 * n), int)

#d1, d2をベクトルに変換する
vec = []
i = 0
while i ** 2 <= d1 // 2:
    d = d1 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
                if i > 0:
                    vec.append([-j, i])
            if j > 0:
                vec.append([-i, j])
        j += 1
    i += 1
i = 0
while i ** 2 <= d2 // 2:
    d = d2 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
                if i > 0:
                    vec.append([-j, i])
            if j > 0:
                vec.append([-i, j])
        j += 1
    i += 1

result = []
count = 0
for y in range(2 * n):
    for x in range(2 * n):
        if table[x][y] == 0:
            result.append([x, y])
            count += 1
            if count == n ** 2:
                break
            for v in vec:
                if max(x + v[0], y + v[1]) < 2 * n and x + v[0] >= 0:
                    table[x + v[0]][y + v[1]] = 1
    else:
        continue
    break
for r in result:
    print(r[0],r[1])

Submission status: Wrong Answer

Solution code:
import numpy as np
n, d1, d2 = map(int, input().split())

table = np.zeros((2 * n, 2 * n), int)

#d1, d2をベクトルに変換する
vec = []
i = 0
while i ** 2 <= d1 // 2:
    d = d1 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
        j += 1
    i += 1
i = 0
while i ** 2 <= d2 // 2:
    d = d2 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
        j += 1
    i += 1
    
result = []
count = 0
for y in range(2 * n):
    for x in range(2 * n):
        if table[x][y] == 0:
            result.append([x, y])
            count += 1
            if count == n ** 2:
                break
            for v in vec:
                if max(x + v[0], y + v[1]) < 2 * n:
                    table[x + v[0]][y + v[1]] = 1
    else:
        continue
    break
for r in result:
    print(r[0],r[1])

Submission status: Wrong Answer

Solution code:
import numpy as np
n, d1, d2 = map(int, input().split())

table = np.zeros((2 * n, 2 * n), int)

#d1, d2をベクトルに変換する
vec = []
i = 0
while i ** 2 < d1:
    d = d1 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
        j += 1
    i += 1
i = 0
while i ** 2 < d2:
    d = d2 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
        j += 1
    i += 1
    
result = []
count = 0
for y in range(2 * n):
    for x in range(2 * n):
        if table[x][y] == 0:
            result.append([x, y])
            count += 1
            if count == n ** 2:
                break
            for v in vec:
                if max(x + v[0], y + v[1]) < 2 * n:
                    table[x + v[0]][y + v[1]] = 1
    else:
        continue
    break
for r in result:
    print(r[0],r[1])

Submission status: Wrong Answer

Solution code:
import numpy as np
n, d1, d2 = map(int, input().split())

table = np.zeros((2 * n, 2 * n), int)

#d1, d2をベクトルに変換する
vec = []
i = 0
while i ** 2 < d1:
    d = d1 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
        j += 1
    i += 1
i = 0
while i ** 2 < d2:
    d = d2 - i ** 2
    j = 0
    while j ** 2 <= d:
        if j ** 2 == d:
            vec.append([i, j])
            if i != j:
                vec.append([j, i])
        j += 1
    i += 1
    
result = []
for y in range(2 * n):
    for x in range(2 * n):
        if table[x][y] == 0:
            result.append([x, y])
            for v in vec:
                if max(x + v[0], y + v[1]) < 2 * n:
                    table[x + v[0]][y + v[1]] = 1
for r in result:
    print(r[0],r[1])

Submission status: Wrong Answer

Solution code:
def check_odd(i, j):
    return (i + j) % 2 == 0


def check_even(i, j):
    return i % 2 == 0


def solve(n, d1, d2):
    s1, s2 = 0, 0
    while d1 % 4 == 0:
        d1 >>= 2
        s1 += 1
    while d2 % 4 == 0:
        d2 >>= 2
        s2 += 1

    f1 = check_odd if d1 % 2 else check_even
    f2 = check_odd if d2 % 2 else check_even
    lim = n ** 2

    buf = []
    cnt = 0
    for i in range(2 * n):
        _i1 = i >> s1
        _i2 = i >> s2
        for j in range(2 * n):
            if f1(_i1, j >> s1) and f2(_i2, j >> s2):
                buf.append('{} {}'.format(i, j))
                cnt += 1
                if cnt == lim:
                    break
    return buf


n, d1, d2 = map(int, input().split())
print('\n'.join(solve(n, d1, d2)))

Submission status: Wrong Answer

Solution code:
from math import ceil, floor, sqrt
from itertools import product

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

# 「x * x + y * y = D」となる(x, y)を求める
didjs = []
for D in [D1, D2]:
    for x in range(ceil(sqrt(D / 2)), floor(sqrt(D)) + 1):
        y = sqrt(D - x * x)
        if y == int(y):
            y = int(y)
#            didjs += [(x, y), (y, x), (-x, y), (-y, x)] # WA
            didjs += [(x, y), (y, x), (x, -y), (y, -x)] # 修正

didjs = set(didjs)

# 各点(i, j)に対して、処理を行う
ans = []
flgs = [[True] * (2 * N) for j in range(2 * N)]
for i, j in product(range(2 * N), repeat=2):
    if flgs[i][j]:
        # 点(i, j)が候補に残っているならば、「いい集合」に追加する
        ans += [(i, j)]
        if len(ans) == N * N: break

        # 点(i, j)から距離√Dの点を、候補から除外する
        for di, dj in didjs:
            if 0 <= i + di < 2 * N and 0 <= j + dj < 2 * N:
                flgs[i + di][j + dj] = False

for i, j in ans:
    print(i, j)

Submission status: Wrong Answer

Solution code:
from math import ceil, floor, sqrt
from itertools import product

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

# 「x * x + y * y = D」となる(x, y)を求める
didjs = []
for D in [D1, D2]:
    for x in range(ceil(sqrt(D / 2)), floor(sqrt(D)) + 1):
        y = sqrt(D - x * x)
        if y == int(y):
            y = int(y)
            didjs += [(x, y), (y, x), (-x, y), (-y, x)]

didjs = set(didjs)

# 各点(i, j)に対して、処理を行う
ans = []
flgs = [[True] * (2 * N) for j in range(2 * N)]
for i, j in product(range(2 * N), repeat=2):
    if flgs[i][j]:
        # 点(i, j)が候補に残っているならば、「いい集合」に追加する
        ans += [(i, j)]
        if len(ans) == N * N: break

        # 点(i, j)から距離√Dの点を、候補から除外する
        for di, dj in didjs:
            if 0 <= i + di < 2 * N and 0 <= j + dj < 2 * N:
                flgs[i + di][j + dj] = False

for i, j in ans:
    print(i, j)

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()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    d = [d1, d2]

    for i in xrange(2):
        dist = set()
        for dx in xrange(2*n):
            dy2 = d[i] - dx**2
            if dy2 < 0: continue
            dy = isqrt(dy2)
            if dy**2 != dy2: continue

            for sx in [1, -1]:
                for sy in [1, -1]:
                    dist.add((sx*dx, sy*dy))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for xi, yi in que:
                            if vis[xi][yi]: continue
                            vis[xi][yi] = True
                            a[xi][yi] += c
                            for dx, dy in dist:
                                if 0 <= x+dx < 2*n and 0 <= y+dy < 2*n and not vis[x+dx][y+dy]:
                                    que2.append((x+dx, y+dy))
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


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:
#!/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()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    d = [d1, d2]

    for i in xrange(2):
        dist = []
        for dx in xrange(2*n):
            dy2 = d[i] - dx**2
            if dy2 < 0: continue
            dy = isqrt(dy2)
            if dy**2 != dy2: continue

            for sgn in [1, -1]:
                if dx*dy == 0 and sgn == -1: continue
                dist.append((dx, sgn*dy))
                dist.append((-dx, -sgn*dy))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for dx, dy in dist:
                            if 0 <= x+dx < 2*n and 0 <= y+dy < 2*n and not vis[x+dx][y+dy]:
                                vis[x+dx][y+dy] = True
                                a[x+dx][y+dy] += c
                                que2.append((x+dx, y+dy))
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


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:
#!/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()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    g = [collections.defaultdict(list) for _ in xrange(2)]
    d = [d1, d2]

    for i in xrange(2):
        for dx in xrange(2*n):
            dy2 = d[i] - dx**2
            if dy2 < 0: continue
            dy = isqrt(dy2)
            if dy**2 != dy2: continue

            for x in xrange(2*n):
                for y in xrange(2*n):
                    if 0 <= x+dx < 2*n and 0 <= y+dy < 2*n:
                        g[i][(x, y)].append((x+dx, y+dy))
                        g[i][(x+dx, y+dy)].append((x, y))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for v in que:
                            if vis[v[0]][v[1]]: continue
                            vis[v[0]][v[1]] = True
                            a[v[0]][v[1]] += c
                            que2 += g[i][v]
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


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:
#!/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()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    g = [collections.defaultdict(list) for _ in xrange(2)]
    d = [d1, d2]

    for i in xrange(2):
        for x1 in xrange(2*n):
            for x2 in xrange(x1, 2*n):
                dy2 = d[i] - (x1-x2) ** 2
                if dy2 >= 0:
                    dy = isqrt(dy2)**2
                    if dy**2 != dy2: continue
                    for y1 in xrange(2*n):
                        for sgn in [1, -1]:
                            if dy == 0 and sgn == -1: continue
                            y2 = y1 + sgn*dy
                            if not 0 <= y2 < 2*n: continue
                            if x1 == x2 and y1 < y2: continue
                            g[i][(x1, y1)].append((x2, y2))
                            g[i][(x2, y2)].append((x1, y1))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for v in que:
                            if vis[v[0]][v[1]]: continue
                            vis[v[0]][v[1]] = True
                            a[v[0]][v[1]] += c
                            que2 += g[i][v]
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


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:
#!/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()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    g = [collections.defaultdict(list) for _ in xrange(2)]
    d = [d1, d2]

    for i in xrange(2):
        for x1 in xrange(2*n):
            for x2 in xrange(x1, 2*n):
                dy2 = d[i] - (x1-x2) ** 2
                if dy2 >= 0:
                    dy = isqrt(dy2)**2
                    if dy**2 != dy2: continue
                    for y1 in xrange(2*n):
                        for sgn in [1, -1]:
                            if dy == 0 and sgn == -1: continue
                            y2 = y1 + sgn*dy
                            if not 0 <= y2 < 2*n: continue
                            if x1 == x2 and y1 < y2: continue
                            g[i][(x1, y1)].append((x2, y2))
                            g[i][(x2, y2)].append((x1, y1))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for v in que:
                            if vis[v[0]][v[1]]: continue
                            vis[v[0]][v[1]] = True
                            a[v[0]][v[1]] += c
                            que2 += g[i][v]
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if v >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


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:
def judge(D):
  n = 0
  while D%4==0:
    n += 1
    D //= 4

  return lambda x,y: ~((x>>n)^(y>>n))&1 if D%2==1 else lambda x,y: ~(x>>n)&1

N,D1,D2 = map(int,input().split())
j1,j2 = judge(D1),judge(D2)
for _,(x,y) in zip(range(N*N),filter(lambda p: j1(*p) and j2(*p), ((x,y) for x in range(N*2) for y in range(N*2)))):
  print(x,y)

Submission status: Wrong Answer

Solution code:
from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  banned = list()
  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)

        for a,b in {(x,y),(y,x)}:
          for s,t in product((1,-1), repeat=2):
            banned.append((s*a,t*b))

  M = N*2

  grid = np.zeros((M,M), dtype=int)

  p0 = (0,0)
  while p0:
    stack = [p0]
    grid[stack[0]] = 1
    while stack:
      x,y = stack.pop()
      t = grid[x,y]
      for dx,dy in banned:
        xx,yy = x+dx,y+dy
        if 0 <= xx < M and 0 <= yy < M and grid[xx,yy] == 0:
          grid[xx,yy] = -t
          stack.append((xx,yy))

    l = np.transpose(np.nonzero(grid==0))
    if l.size > 0:
      p0 = tuple(l[0])
    else:
      p0 = None

  print('A')
  return grid

N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N,D1)
g2 = helper(N,D2)

if np.count_nonzero(g1==1)*2 > M*M:
  g1 = g1==1
else:
  g1 = g1==-1

if np.sum(g1*g2) > 0:
  ans = g1&(g2==1)
else:
  ans = g1&(g2==-1)


# for x,y in np.transpose(np.nonzero(ans))[:N*N]:
#   print(x,y)

print(ans.astype(int))
print(np.sum(ans), N*N)

Submission status: Wrong Answer

Solution code:
n, d1, d2 = map(int, raw_input().split())
import random
pts = []
while len(pts) != n * n:
	x = random.randint(0, 2 * n - 1)
	y = random.randint(0, 2 * n - 1)
	if not (x, y) in pts:
		pts.append((x, y))

for pt in pts:
	print pt[0], pt[1]