problem statement
In this problem you have to count the number of nonesquare 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 += (wj+1) * (hi+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, (width2+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...

Mathematics As you can see in the problem description, you have to find numbers a & b such that (a, b) = G and [a, b] = L and also it ...

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

I don't know why, but I had a great misunderstanding of the problem statement from this sentence "FJ pours milk from one bucket t...
No comments:
Post a Comment