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

36 77 8
[Finished in 0.5s]

# ((1+m)*m/2)*((1+n)*n/2) = 2000000 ->  n*m*(n+1)*(m+1) = 8000000

nearest = 1000000
for i in range(1,1000):
        for j in range(1,1000):
                near = abs(8000000 - i*j*(i+1)*(j+1))
                if nearest > near:
                        nearest = near
                        neari = i
                        nearj = j
print (neari,nearj,nearest)

芒果加黄桃

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

36 77 2
cost 0.006001 sec

fc1735

def f(x):
  return x * (x + 1) // 2

target = int(2*10**6)
curr = 0
ans = 0
for i in range(1, 999999999999):
  a = f(i)
  for j in range(1, i + 1):
    b = f(j)
    if abs(curr - target) > abs(a * b - target):
      curr = a * b
      ans = i * j
    if a * b > target:
      break
  if a > target:
    break

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.

#include<iostream>
#include<cstdlib>
using namespace std;

const int M = 2001;
const int STANDARD = 2e6;

int Cn_2(int n){
  return n*(n-1)/2;
}

int main(){
  int dif = 2e6;//已经充分大
  int ans;
  for (int m = 1;m <= M;m++){
    for (int n = m;n <= M;n++){
      int t = Cn_2(n+1) * Cn_2(m+1);//矩形总个数公式
      if (abs(t-STANDARD) < dif)  {dif = abs(t-STANDARD); ans = m*n;}

      if (t > STANDARD) break;//由组合数的递增可知，后面的总个数必然不会更接近2e6
    }
  }
  cout << ans << endl;
  return 0;
}

永恒的蓝色梦想

C++ 0ms

/*
            m
  ┏━━━━━━━━━┓
  ┃                  ┃
n ┃                  ┃
  ┃                  ┃
  ┗━━━━━━━━━┛

(m(m+1)/2)(n(n+1)/2)=2e6
m(m+1)n(n+1)=8e6
m(m+1)=8e6/n(n+1)
m=(sqrt(3.2e7/n(n+1)+1)-1)/2
 =sqrt(8e6/n(n+1)+0.25)-0.5
*/
#include<iostream>
#include<limits>
#include<cmath>



int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    const int UPPER_BOUND = ceil(sqrt(4e6 + 0.25) - 0.5);//n=1
    int n, m, temp, s = 0, diff, min_diff = numeric_limits<int>::max();
    double m_;


    for (n = 1; n <= UPPER_BOUND; n++) {
        temp = n * (n + 1);

        m = m_ = sqrt(8e6 / temp + 0.25) - 0.5;
        diff = abs(8000000 - m * (m + 1) * temp);

        if (diff < min_diff) {
            min_diff = diff;
            s = m * n;
        }

        m = ceil(m_);
        diff = abs(8000000 - m * (m + 1) * temp);

        if (diff < min_diff) {
            min_diff = diff;
            s = m * n;
        }
    }


    cout << s << endl;
    return 0;
}

guosl

/*
答案：2772
耗时：0.015695秒
      0.0043418秒（六核）
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;

int main(void)
{
  double t = omp_get_wtime();
  long long nArea = 0, nCount = 0;
#pragma omp parallel for shared(nArea,nCount) collapse(2)
  for (int m = 1; m <= 100; ++m)//枚举大矩形
  {
    for (int n = 1; n <= 100; ++n)
    {
      long long nCount1 = 0;
      for (int l = 0; l <= m - 1; ++l)//枚举矩形的左上点
      {
        for (int u = 0; u <= n - 1; ++u)
          nCount1 += (m - l)*(n - u);
      }
      if (abs(nCount1 - 2000000) < abs(nCount - 2000000))//选择矩形数最靠近2000000的大矩形
      {
#pragma omp critical
        {
          //保留结果
          //防止其它线程已经改写了数据，再次确认
          if (abs(nCount1 - 2000000) < abs(nCount - 2000000))
          {
            nCount = nCount1;
            nArea = m;
            nArea *= n;
          }
        }
      }
    }
  }
  t = omp_get_wtime() - t;
  cout << nArea << endl << t << endl;
  return 0;
}