题目描述

给定一个整数 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

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000010
#define PI acos(-1)
using namespace std;
struct In
{
ll int x;
ll int y;
ll int z;
ll int sum;
}a[100000];
int cmp( const void *a ,const void *b)
{
return (*(In *)a).sum > (*(In *)b).sum ? 1 : -1;
}
int main()
{   int n,t,ans;int k=0;

    scanf("%d",&t);
    while(t--){k=0;
        scanf("%d",&n);
        for(ll int i=0;i<=n/3;i++)for(ll int j=0;j<=(n-3*i)/5;j++){
            ans=n-3*i-5*j;
            if(ans%7==0&&ans/7>=0){a[k].x=i;a[k].y=j;a[k].z=ans/7;a[k].sum=a[k].x+a[k].y+a[k].z;k++;}
        }

        if(k==0)printf("-1\n");
        else {qsort(a,k,sizeof(a[0]),cmp);
        printf("%lld %lld %lld\n",a[0].x,a[0].y,a[0].z);}
    }
    return 0;
}