题目描述

给定一个整数 n，请你求出三元一次方程 3x+5y+7z=n 的一组非负整数解。

要求：

x≥0,y≥0,z≥0
如果解不唯一，则输出 x,y,z 字典序最小的解。

输入格式

第一行包含一个整数 T，表示共有 T 组测试数据。

每组数据占一行，包含一个整数 n。

输出格式

每组数据输出一行结果，如果无解则输出 −1，否则输出 x,y,z，整数之间单个空格隔开。

数据范围

对于前三个测试点，1≤n≤100。
对于全部测试点，1≤T≤1000，1≤n≤1000。

输入样例

4
30
67
4
14

输出样例

0 6 0
0 5 6
-1
0 0 2

思路

暴力，3重循环，由于只要求一组字典序最小的解，直接从z开始从小到大枚举

C++ 代码

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{

    int n,i,j,k;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for( i=0; i<=1000; i++)
        {
            if(3*i>n)break; //超出范围停止循环
            for(j=0; j<=1000; j++)
            {
                if(5*j>n)break;//同上

                for(k=0; k<=1000; k++)
                {
                    if(3*i+5*j+7*k==n)break;//搜索完成
                    if(7*k>n)break;
                }
                if(3*i+5*j+7*k==n)break;//满足条件就break
            }
            if(3*i+5*j+7*k==n)break;//同上
        }
        if(3*i+5*j+7*k==n)//判断是否找到符合条件的数
            printf("%d %d %d\n",i,j,k);
        else cout<<-1<<endl;
    }
    return 0;
}