-
Notifications
You must be signed in to change notification settings - Fork 0
/
p085.py
42 lines (30 loc) · 821 Bytes
/
p085.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# -*- coding: utf-8 -*-
"""
Created on Mon Jul 27 11:59:01 2020
@author: zhixia liu
"""
"""
Project Euler 85: Counting rectangles
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.
"""
#%% naive
# n(n+1)m(m+1)/4 = 2,000,000
from math import sqrt
# initialize
def squares(n,m):
return n*(n+1)*m*(m+1)/4
def diff(n,m):
return abs(squares(n,m)-2000000)
n = m = int(sqrt(sqrt(2000000)))
nearest = (n,m)
mindiff = diff(n,m)
while n>0:
if squares(n,m)>2000000:
n -= 1
else:
m += 1
if diff(n,m)<mindiff:
nearest = (n,m)
mindiff = diff(n,m)
print(nearest)