题目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.

题目：

仔细数的话可以看出一个 3×2 的矩形网格里包含 18 个矩形：

虽然没有哪个矩形网格包含正好两百万个矩形，找出包含最接近两百万个矩形的矩形网格的面积。

jerryxjr1220

1. 36 77 8
   
2. [Finished in 0.5s]
   
3. 
   
4. # ((1+m)*m/2)*((1+n)*n/2) = 2000000 ->  n*m*(n+1)*(m+1) = 8000000
   
5. 
   
6. nearest = 1000000
   
7. for i in range(1,1000):
   
8.         for j in range(1,1000):
   
9.                 near = abs(8000000 - i*j*(i+1)*(j+1))
   
10.                 if nearest > near:
    
11.                         nearest = near
    
12.                         neari = i
    
13.                         nearj = j
    
14. print (neari,nearj,nearest)

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 找出包含最接近200万个矩形的面积
   
3. from time import time
   
4. def euler085(N=2000000):
   
5.     a, b, t = 0, 0, N
   
6.     for i in range(1, int((4 * N) ** 0.25 + 1)):
   
7.         for j in range(1, int(((4 * N) / i ** 2) ** 0.5 + 1)):
   
8.             tmp = (i * (i + 1) * j * (j + 1) / 4)
   
9.             if  abs(tmp - N) < t:
   
10.                 t = abs(tmp - N)
    
11.                 a, b = i, j
    
12.             if tmp > N and abs(tmp - N) > t:
    
13.                 break
    
14.     print(a, b, int(t))
    
15. if __name__ == '__main__':
    
16.     start = time()
    
17.     euler085()
    
18.     print('cost %.6f sec' % (time() - start))
    

复制代码

36 77 2
cost 0.006001 sec

fc1735

1. def f(x):
   
2.   return x * (x + 1) // 2
   
3. 
   
4. target = int(2*10**6)
   
5. curr = 0
   
6. ans = 0
   
7. for i in range(1, 999999999999):
   
8.   a = f(i)
   
9.   for j in range(1, i + 1):
   
10.     b = f(j)
    
11.     if abs(curr - target) > abs(a * b - target):
    
12.       curr = a * b
    
13.       ans = i * j
    
14.     if a * b > target:
    
15.       break
    
16.   if a > target:
    
17.     break
    
18. 
    
19. print(ans)

复制代码

https://github.com/devinizz/project_euler/blob/master/page02/85.py

debuggerzh

2772

Process returned 0 (0x0)   execution time : 0.029 s
Press any key to continue.

1. #include<iostream>
   
2. #include<cstdlib>
   
3. using namespace std;
   
4. 
   
5. const int M = 2001;
   
6. const int STANDARD = 2e6;
   
7. 
   
8. int Cn_2(int n){
   
9.   return n*(n-1)/2;
   
10. }
    
11. 
    
12. int main(){
    
13.   int dif = 2e6;//已经充分大
    
14.   int ans;
    
15.   for (int m = 1;m <= M;m++){
    
16.     for (int n = m;n <= M;n++){
    
17.       int t = Cn_2(n+1) * Cn_2(m+1);//矩形总个数公式
    
18.       if (abs(t-STANDARD) < dif)  {dif = abs(t-STANDARD); ans = m*n;}
    
19. 
    
20.       if (t > STANDARD) break;//由组合数的递增可知，后面的总个数必然不会更接近2e6
    
21.     }
    
22.   }
    
23.   cout << ans << endl;
    
24.   return 0;
    
25. }
    

复制代码

永恒的蓝色梦想

C++ 0ms

1. /*
   
2.             m
   
3.   ┏━━━━━━━━━┓
   
4.   ┃                  ┃
   
5. n ┃                  ┃
   
6.   ┃                  ┃
   
7.   ┗━━━━━━━━━┛
   
8. 
   
9. (m(m+1)/2)(n(n+1)/2)=2e6
   
10. m(m+1)n(n+1)=8e6
    
11. m(m+1)=8e6/n(n+1)
    
12. m=(sqrt(3.2e7/n(n+1)+1)-1)/2
    
13. =sqrt(8e6/n(n+1)+0.25)-0.5
    
14. */
    
15. #include<iostream>
    
16. #include<limits>
    
17. #include<cmath>
    
18. 
    
19. 
    
20. 
    
21. int main() {
    
22.     using namespace std;
    
23.     ios::sync_with_stdio(false);
    
24. 
    
25.     const int UPPER_BOUND = ceil(sqrt(4e6 + 0.25) - 0.5);//n=1
    
26.     int n, m, temp, s = 0, diff, min_diff = numeric_limits<int>::max();
    
27.     double m_;
    
28. 
    
29. 
    
30.     for (n = 1; n <= UPPER_BOUND; n++) {
    
31.         temp = n * (n + 1);
    
32. 
    
33.         m = m_ = sqrt(8e6 / temp + 0.25) - 0.5;
    
34.         diff = abs(8000000 - m * (m + 1) * temp);
    
35. 
    
36.         if (diff < min_diff) {
    
37.             min_diff = diff;
    
38.             s = m * n;
    
39.         }
    
40. 
    
41.         m = ceil(m_);
    
42.         diff = abs(8000000 - m * (m + 1) * temp);
    
43. 
    
44.         if (diff < min_diff) {
    
45.             min_diff = diff;
    
46.             s = m * n;
    
47.         }
    
48.     }
    
49. 
    
50. 
    
51.     cout << s << endl;
    
52.     return 0;
    
53. }

复制代码

guosl

1. /*
   
2. 答案：2772
   
3. 耗时：0.015695秒
   
4.       0.0043418秒（六核）
   
5. */
   
6. #include <iostream>
   
7. #include <algorithm>
   
8. #include <omp.h>
   
9. using namespace std;
   
10. 
    
11. int main(void)
    
12. {
    
13.   double t = omp_get_wtime();
    
14.   long long nArea = 0, nCount = 0;
    
15. #pragma omp parallel for shared(nArea,nCount) collapse(2)
    
16.   for (int m = 1; m <= 100; ++m)//枚举大矩形
    
17.   {
    
18.     for (int n = 1; n <= 100; ++n)
    
19.     {
    
20.       long long nCount1 = 0;
    
21.       for (int l = 0; l <= m - 1; ++l)//枚举矩形的左上点
    
22.       {
    
23.         for (int u = 0; u <= n - 1; ++u)
    
24.           nCount1 += (m - l)*(n - u);
    
25.       }
    
26.       if (abs(nCount1 - 2000000) < abs(nCount - 2000000))//选择矩形数最靠近2000000的大矩形
    
27.       {
    
28. #pragma omp critical
    
29.         {
    
30.           //保留结果
    
31.           //防止其它线程已经改写了数据，再次确认
    
32.           if (abs(nCount1 - 2000000) < abs(nCount - 2000000))
    
33.           {
    
34.             nCount = nCount1;
    
35.             nArea = m;
    
36.             nArea *= n;
    
37.           }
    
38.         }
    
39.       }
    
40.     }
    
41.   }
    
42.   t = omp_get_wtime() - t;
    
43.   cout << nArea << endl << t << endl;
    
44.   return 0;
    
45. }

复制代码