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)
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
Returns22See 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
View Code1 #include
2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 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\n" , 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\n" , 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 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 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 &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 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 已知一个长 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
-