题目描述
给定一个整数 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
算法1
若n<7,1、2、4无解,3=3,5=5, 6 = 23;
若14>n>=7,先枚举出7~13的最大字典序解:
7 = 7
8 = 3+5
9 = 33
10 = 25
11 = 23+5
12 = 5+7;
13 = 3+5+5;
若n>=14,则减去k个7使余下的数在7~13之间
最后,可以将3+7转化为5+5降低字典序
时间复杂度:$O(1)$
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
int n,x,res[3];
int main()
{
cin >> n;
while(n--){
memset(res, 0, sizeof(res));
cin >> x;
if(x==1||x==2||x==4){cout<<"-1\n";
continue;}
if(x==3)res[0] = 1;
if(x==5)res[1] = 1;
if(x==6)res[0] = 2;
if(x>=7){//枚举7~13的解
int k = x/7;
x = x%7 + 7;
if(x==7){res[2]=1;}
if(x==8){
res[0]=1;
res[1]=1;
}
if(x==9){
res[0]=3;
}
if(x==10){
res[1]=2;
}
if(x==11){
res[0]=2;
res[1]=1;
}
if(x==12){
res[1] = 1;
res[2] = 1;
}
if(x==13){
res[0] = 1;
res[1] = 2;
}
res[2]+=k-1;
if(res[0]!=0&&res[2]!=0){//将3+7转化为5+5
if(res[0]<=res[2]){
res[1]+=res[0]*2;
res[2]-=res[0];
res[0]=0;
}
else{
res[0]-=res[2];
res[1]+=res[2]*2;
res[2]=0;
}
}
}
printf("%d %d %d\n",res[0],res[1],res[2]);
}
return 0;
}