SRM 552

As usual I only know how to do the 250 problem, and I failed that one.

p250, given three numbers R, G, B, and another number N, you lay out a triangle such that no two neighboring balls share same color. The problem asks how many triangles with N layers you can make.

It is easy to see that you need

N R G B
-------------
1 0 0 0
2 1 1 1
3 2 2 2
4 4 3 3
5 5 5 5
6 7 7 7

Enough pattern, so to make one triangle of N layers you need sum of 1 to N balls, which is N(N+1)/2. For N=3k or 3k+2 this number is a multiple of 3 so you need the same number of three colors, and the answer is simply B/(S/3), where R>=G>=B and S = N(N+1)/2.

The tricky case is N=3k+1, then S = 3k' + 1. Now you need to distribute balls to make max number of triangles. Let us image that the optimal answer is m triangles, then you need at least m*((S-1)/3) for each color, and whatever remain can be any color, as long as the remaining balls are at least m. So the answer is min of (R+G+B)/S and B/(S/3). The special case is N=1, where you return R+G+B. An easier way to visualize this is that you grow three equal columns for each color, then what has been cut off from each color are the remaining balls you have, those balls are equivalent and can be distributed to any triangle you want to make.

The problem setter is more evil than this to introduce a few integer overflow even for long long, if you use * instead of /

p500
notice that the two rectangles r1 and r2, can be separated by a horizontal or vertical divider. Try all possible dividers and within each region, brute-force on all possible r1, and of all possible r2 respectively. We have no more than 30 horizontal divider and same for vertical ones. To try all possible r1, just run (x1,y1) and (x2,y2). This is no more than 30*30*30*30 < 10^6. The implementation demands extreme care. Draw a picture to get the indices correct. Also check when there is no solution, you need to return -1. This is different from the case when there is zero flowers.

p1000