SRM 552

第二题推出数学公式后发现太坑爹了。。

### oblem Statement

A *Ball Triangle* is a set of identical balls placed in a triangular shape. A Ball Triangle has **N** rows, numbered 1 to **N** from top to bottom. For all i, 1 <= i <= **N**, the i-th row contains i balls. For example, the following image shows a Ball Triangle with **N**=3.

![](https://www.ccppcoding.com/wp-content/uploads/BallTrig-1.png)

Fox Jiro has infinitely many Ball Triangles. He can paint a Ball Triangle according to the following conditions:

* Each of the balls has to be painted either red, green, or blue.
* No two adjacent balls may share the same color.

The following image shows one valid coloring of a Ball Triangle for **N**=3.

![](https://www.ccppcoding.com/wp-content/uploads/BallTrig-2.png)

Jiro wants to paint as many Ball Triangles as he can. As long as he follows the rules above, he may color the Ball Triangles in any way he likes. Some of the colored Ball Triangles may look exactly the same, but they don't have to. The only other constraint is the total amount of paint available to Jiro: In all the triangles together, he can paint at most **R** balls red, **G** balls green, and **B** balls blue.

You are given the longs **R**, **G**, and **B**. You are also given the int **N**. Return the maximum possible number of Ball Triangles Jiro can paint.

### Definition

Class:	FoxPaintingBalls
Method:	theMax
Parameters:	long, long, long, int
Returns:	long
Method signature:	long theMax(long R, long G, long B, int N)
(be sure your method is public)

### Constraints

- **R**, **G** and **B** will each be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.

- **N** will be between 1 and 1,000,000,000, inclusive.

### Examples

Returns: 1

Jiro can paint one Ball Triangle in the same way as in the image in the statement.

Returns: 0

This time Jiro can paint no Ball Triangles.

Returns: 2

Returns: 2

Returns: 30

19330428391852493

48815737582834113

11451481019198930

Returns: 5750952686

Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

给出N求最多可以画多少？

一个规律

给出N，那么一共有M=N*(N+1)/2个球，那么画出一个满足目标的Triangle Ball需要的球的组合设为a个R球，b个G球，c个B球。

d=M/3; a,b,c就是和d接近的三个数。

如果M%3==0，那么a=b=c等于d，这样去R,G,B中最小的一个数除a就可以得到结果了。即return min(R,G,B)/a;

如果M%3==1或==2，设这一组数为d, d, d+1或者d+1,d+1,d。

a=b=d，c=d+1或者a=b=d+1，c=d。

因为a,b总相等，那么这一组数有3中排列方式。

(a,b,c)

(a,c,b)

(c,a,b)

设第一组使用了x个，第二组使用了y个，第三组使用了z个。

所求目标是max: x+y+z

注意，我们有

xa+ya+z*c=R

xb+yc+z*a=G

xc+yb+z*b=B

左右相加，我们得到

x(a+b+c)+y(a+b+c)+z*(a+b+c)=R+G+B

整理，得到

(x+y+z)=(R+G+B)/(a+b+c)

所以x+y+z居然是固定的值！！

所以只要return (R+G+B)/(a+b+c)就可以了！

public class FoxPaintingBalls {

    public long theMax(long R, long G, long B, int N){
        long a, b, c;
        long M=N*(N+1)/2;
        long rm=M%3;
        a=b=c=(M/3);
        if(rm==1){
            c++;
        }
        if(rm==2){
            a++;
            b++;
        }
        if(rm==0){
            return Math.min(Math.min(R/a, G/a), B/a);
        } else {
            return (R+G+B)/(a+b+c);
        }
    }
}

如果没有注意到这个推倒而直接写一个递归函数的，就惨了，

像这样的。

private long getMax(long R, long G, long B, long a, long b, long c){
        if((R==b&&G==a&&B==c)||(R==c&&G==b&&B==a)||(R==b&&G==c&&B==a)){
            return 1;
        }
        else{
            long x,y,z;
            x=R-a;y=G-b;z=B-c;
            long max1=0,max2=0,max3=0;
            if(x>=0&&y>=0&&z>=0){
                max1=getMax(x,y,z,a,b,c)+1;
            }
            x=R-a;y=G-c;z=B-b;
            if(x>=0&&y>=0&&z>=0){
                max2=getMax(x,y,z,a,b,c)+1;
            }
            x=R-c;y=G-a;z=B-b;
            if(x>=0&&y>=0&&z>=0){
                max3=getMax(x,y,z,a,b,c)+1;
            }
            return Math.max(Math.max(max1, max2), max3);
        }
    }

原文链接: https://www.cnblogs.com/gaoqichao/archive/2012/08/17/2643811.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/59868

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

SRM 552

相关推荐