tc 146 2 RectangularGrid(数学推导）

SRM 146 2 500RectangularGrid

Problem Statement

Given the width and height of a rectangular grid, return the total number of rectangles (NOT counting squares) that can be found on this grid.

For example, width = 3, height = 3 (see diagram below):

 __ __ __
|__|__|__|
|__|__|__|
|__|__|__|

In this grid, there are 4 2x3 rectangles, 6 1x3 rectangles and 12 1x2 rectangles. Thus there is a total of 4 + 6 + 12 = 22 rectangles. Note we don't count 1x1, 2x2 and 3x3 rectangles because they are squares.

Definition

ClassRectangularGrid
MethodcountRectangles
Parametersint , int
Returnslong long
Method signaturelong long countRectangles(int width, int height)

(be sure your method is public)

Limits

Time limit (s)2.000
Memory limit (MB)64

Notes

rectangles with equals sides (squares) should not be counted.

Constraints

width and height will be between 1 and 1000 inclusive.

Test cases

- width3
- height3
Returns22

See above
- width5
- height2
Returns31
```
 __ __ __ __ __
|__|__|__|__|__|
|__|__|__|__|__|
```
In this grid, there is one 2x5 rectangle, 2 2x4 rectangles, 2 1x5 rectangles, 3 2x3 rectangles, 4 1x4 rectangles, 6 1x3 rectangles and 13 1x2 rectangles. Thus there is a total of 1 + 2 + 2 + 3 + 4 + 6 + 13 = 31 rectangles.
- width10
- height10
Returns2640
- width1
- height1
Returns0

width592
height964

Returns81508708664

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <ctime>
  5 #include <iostream>
  6 #include <algorithm>
  7 #include <set>
  8 #include <vector>
  9 #include <sstream>
 10 #include <typeinfo>
 11 #include <fstream>
 12 
 13 using namespace std;
 14 typedef long long ll ;
 15 class RectangularGrid {
 16     public:
 17     long long countRectangles(int l , int r) {
 18         if (l > r) swap (l , r ) ;
 19       //  printf ("l = %d , r = %d
" , l , r ) ;
 20         ll all = (1ll *l*l*r*r + 1ll *l*r*r + 1ll *r*l*l + 1ll *r*l) / 4 ;
 21         ll sum = 1ll * l * (l - 1) * (l + 1) / 3 + 1ll * (r - l + 1) * l * (l + 1) / 2 ;
 22      //   printf ("all = %lld , sum = %lld
" , all , sum) ;
 23         return all - sum ;
 24     }
 25 };
 26 
 27 // CUT begin
 28 ifstream data("RectangularGrid.sample");
 29 
 30 string next_line() {
 31     string s;
 32     getline(data, s);
 33     return s;
 34 }
 35 
 36 template <typename T> void from_stream(T &t) {
 37     stringstream ss(next_line());
 38     ss >> t;
 39 }
 40 
 41 void from_stream(string &s) {
 42     s = next_line();
 43 }
 44 
 45 template <typename T>
 46 string to_string(T t) {
 47     stringstream s;
 48     s << t;
 49     return s.str();
 50 }
 51 
 52 string to_string(string t) {
 53     return """ + t + """;
 54 }
 55 
 56 bool do_test(int width, int height, long long __expected) {
 57     time_t startClock = clock();
 58     RectangularGrid *instance = new RectangularGrid();
 59     long long __result = instance->countRectangles(width, height);
 60     double elapsed = (double)(clock() - startClock) / CLOCKS_PER_SEC;
 61     delete instance;
 62 
 63     if (__result == __expected) {
 64         cout << "PASSED!" << " (" << elapsed << " seconds)" << endl;
 65         return true;
 66     }
 67     else {
 68         cout << "FAILED!" << " (" << elapsed << " seconds)" << endl;
 69         cout << "           Expected: " << to_string(__expected) << endl;
 70         cout << "           Received: " << to_string(__result) << endl;
 71         return false;
 72     }
 73 }
 74 
 75 int run_test(bool mainProcess, const set<int> &case_set, const string command) {
 76     int cases = 0, passed = 0;
 77     while (true) {
 78         if (next_line().find("--") != 0)
 79             break;
 80         int width;
 81         from_stream(width);
 82         int height;
 83         from_stream(height);
 84         next_line();
 85         long long __answer;
 86         from_stream(__answer);
 87 
 88         cases++;
 89         if (case_set.size() > 0 && case_set.find(cases - 1) == case_set.end())
 90             continue;
 91 
 92         cout << "  Testcase #" << cases - 1 << " ... ";
 93         if ( do_test(width, height, __answer)) {
 94             passed++;
 95         }
 96     }
 97     if (mainProcess) {
 98         cout << endl << "Passed : " << passed << "/" << cases << " cases" << endl;
 99         int T = time(NULL) - 1433920510;
100         double PT = T / 60.0, TT = 75.0;
101         cout << "Time   : " << T / 60 << " minutes " << T % 60 << " secs" << endl;
102         cout << "Score  : " << 500 * (0.3 + (0.7 * TT * TT) / (10.0 * PT * PT + TT * TT)) << " points" << endl;
103     }
104     return 0;
105 }
106 
107 int main(int argc, char *argv[]) {
108     cout.setf(ios::fixed, ios::floatfield);
109     cout.precision(2);
110     set<int> cases;
111     bool mainProcess = true;
112     for (int i = 1; i < argc; ++i) {
113         if ( string(argv[i]) == "-") {
114             mainProcess = false;
115         } else {
116             cases.insert(atoi(argv[i]));
117         }
118     }
119     if (mainProcess) {
120         cout << "RectangularGrid (500 Points)" << endl << endl;
121     }
122     return run_test(mainProcess, cases, argv[0]);
123 }
124 // CUT end

View Code

已知一个长 l , 宽 r 的由１×１的单位矩阵构成的矩阵，问其中有多少个长方形？

那么我们只要求出其中矩阵的总个数n , 和正方形数m,然后n - m就是答案。

ｎ＝ｌ*ｒ　＋　ｌ×（ｒ×（ｒ－１））／２　＋　ｒ×（ｌ×（ｌ－１））／２　＋　ｌ×ｒ×（ｌ－１）×（ｒ－１）／４

　＝（ｌ×ｌ×ｒ×ｒ＋ｌ×ｒ×ｒ＋ｒ×ｌ×ｌ＋ｒ×ｌ）／４；

ｍ＝２×（１＋２×３／２＋４×３／２＋……＋ｌ×（ｌ－１）／２）　＋　（ｒ－ｌ＋１）×ｌ×（ｌ＋１）／２；

　＝ｌ×（ｌ＋１）×（２×ｌ＋１）／６　＋　（ｒ－ｌ）×ｌ×（ｌ＋１）／２；

ＰＳ：

1^2 + 2^2 + 3^2 + 4^2 + 5^2 +……＋n^2 = n*(n + 1)*(2*n+1)/6;

证明：（来自百度文库）

想像一个有圆圈构成的正三角形，

第一行1个圈，圈内的数字为1

第二行2个圈，圈内的数字都为2，

以此类推

第n行n个圈，圈内的数字都为n，

我们要求的平方和，

就转化为了求这个三角形所有圈内数字的和。

设这个数为r

下面将这个三角形顺时针旋转120度，

得到第二个三角形

再将第二个三角形顺时针旋转120度，得到第三个三角形.

然后，将这三个三角形对应的圆圈内的数字相加，

我们神奇的发现所有圈内的数字都变成了

2n+1

而总共有几个圈呢，这是一个简单的等差数列求和

1+2+……+n=n(n+1)/2

于是

3r=[n(n+1)/2]*(2n+1)

r=n(n+1)(2n+1)/6