34 lines
1.1 KiB
Python
34 lines
1.1 KiB
Python
# By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles.
|
|
# Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
|
|
|
|
import sys
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
@timing
|
|
def p085():
|
|
N = 2000000
|
|
min_diff = sys.maxsize
|
|
|
|
for i in range(1, 100):
|
|
for j in range(1, i + 1):
|
|
# In a 2x3 grid, we can take rectangles of height 2 in 3 ways (two rectangles of heigh
|
|
# one and one of height 2). For the width, we can take 6 rectangles (3 of width 1,
|
|
# 2 of width 2 and 1 of width 3). The total is 6x3=18 rectangles.
|
|
# Extending to m x n, we can take (m+m-1+m-2+...+1)x(n+n-1+n-2+...+1)=
|
|
# m(m + 1) / 2 * n(n + 1) / 2 = m(m + 1) * n(n + 1) / 4 rectangles
|
|
n = (i * (i + 1) * j * (j + 1)) / 4
|
|
diff = abs(N - n)
|
|
|
|
if diff < min_diff:
|
|
min_diff = diff
|
|
area = i * j
|
|
|
|
print('Project Euler, Problem 85')
|
|
print(f'Answer: {area}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p085()
|