problem statement
In this problem you have to count the number of none-square rectangles in a given rectangle.
What I do is this, that I try to count all of
1*2, 1*3 ... 1*w
2*3, 2*4.... 2*w
......................
rectangles.
and I do this once for my rectangle and another time with the new rectangle with width and height swapped.
this is my code:
long long func(int w, int h)
{
long long res = 0;
for(int i = 1; i <= h; i ++)
for(int j = i+1; j <= w; j ++)
res += (w-j+1) * (h-i+1);
return res;
}
long long countRectangles(int w, int h)
{
return func( w, h ) + func( h, w );
}
How did I find this solution? I just tried to check it out on a piece of paper and I saw that there is a template for placing the rectangles with different width and heights in a larger rectangle.
For example if you want to place a 1*2 rectangle in a large rectangle, first you have to count how many of them are placed in a single row, (width-2+1) and multiply this number in height that is the number of 1*2 rectangles that are placed horizontally in a rectangle.
There are another solutions that I'm thinking about them, using 4 and 3 loops that I think they are trivial, and using 1 loop or even no loop that I'm thinking to understand them completely, then I'm gonna add them here.
I describe my solution or give some hints about the solution for algorithmic problems used in ICPC or online sites for programming contests.
Wednesday, January 12, 2011
Subscribe to:
Post Comments (Atom)
USACO - Prime Palindromes
I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...
-
Prime Cryptarithm The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set ...
-
Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing al...
-
Dynamic Programming The problem wants to know in how many ways one can reach destination ( cell[width][height] ) If there were no obstacle...
No comments:
Post a Comment