OpenJudge 2747 数字方格

1.链接地址：

http://bailian.openjudge.cn/practice/2747

2.题目：

总时间限制:

1000ms

内存限制:

65536kB

描述

如上图，有3个 方格，每个方格里面都有一个整数a1，a2，a3。已知0 <= a1, a2, a3 <= n，而且a1 + a2是2的倍数，a2 + a3是3的倍数， a1 + a2 + a3是5的倍数。你的任务是找到一组a1，a2，a3，使得a1 + a2 + a3最大。

输入

输入的第一行是一个数t，表示测试数据的数目。接下来的t行，每行给出一个n (0 <= n <= 100)的值。

输出

对于每一个n的值，输出a1 + a2 + a3的最大值。

样例输入

2
0
3

样例输出

0
5

3.思路：

枚举，使用前两道公式做条件缩小枚举范围，最后判断第三道公式是否成立

由于要求最大，所以采取逆序遍历。每次与一找到的结果的max比较，不可能的话直接跳过

4.代码：

include <iostream>

using namespace std;

int main()
{
    int t;
    cin>>t;

    int n;
    int a1,a2,a3;
    int k1,k2;
    while(t--)
    {
        int max = 0;
        cin>>n;
        for(a1 = n; a1 >= 0; --a1)
        {
            if(a1 + 2 * n < max) break;
            for(k1 = (n + a1) / 2; k1 >= a1 / 2; --k1)
            {
                a2 = 2 * k1 - a1;
                if(a1 + a2 + n < max) break;
                for(k2 = (n + a2) / 3; k2 >= a2 / 3; --k2)
                {
                    a3 = 3 * k2 - a2;
                    if(a1 + a2 + a3 < max) break;
                    if((a1 + a2 + a3) % 5 == 0)
                    {
                        if(max < a1 + a2 + a3) max = a1 + a2 + a3;
                    }
                }
            }
        }
        cout<<max<<endl;
    }
    return 0;
}