Last active
April 8, 2018 02:20
-
-
Save k/8119f133f81b9c505526117a3c147f3d to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Q3 | |
def output(case_num, result): | |
print("Case #{}: {}".format(case_num, str(result))) | |
t = int(input()) | |
MIN = 2 | |
MAX = 999 | |
def area(min_xy, max_xy): | |
x_min, y_min = min_xy | |
x_max, y_max = max_xy | |
return (x_max - x_min) * (y_max - y_min) | |
def num_empty(grid, x, y): | |
count = 0 | |
for i in range(3): | |
x_test = x + (i - 1) | |
if x_test >= 0 and x_test < 1000 : | |
for j in range(3): | |
y_test = y + (j - 1) | |
if y_test >= 0 and y_test < 1000: | |
count += grid[i][j] | |
return count | |
def calculate_next(grid, center, min_xy, max_xy, A): | |
safe = 0 | |
if area(min_xy, max_xy) >= A: | |
safe = 1 | |
x = min_xy[0] + safe | |
y = min_xy[1] + safe | |
score = 0 | |
n = (0, 0) | |
while x <= max_xy[0] - safe: | |
while y <= max_xy[1] - safe: | |
curr = num_empty(grid, x, y) | |
if curr > score: | |
score = curr | |
n = (x, y) | |
y += 1 | |
x += 1 | |
return n | |
for case_num in range(1, t + 1): | |
A = int(input()) | |
i = 1 | |
j = 1 | |
center = (500, 500) | |
min_xy = (500, 500) | |
max_xy = (500, 500) | |
grid = [[ 1 for i in range(1000)] for j in range(1000)] | |
while i != 0 and j != 0: | |
i, j = calculate_next(grid, center, min_xy, max_xy, A) | |
print("{} {}".format(i, j)) | |
i, j = (int(a) for a in input().split(' ')) | |
grid[i][j] = 0 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment