Posted on 2012-03-01 13:50
C小加 阅读(221)
评论(0) 编辑 收藏 引用 所属分类:
解题报告
题目保证至少有一个1、2、3、4。说明这四个数是一个突破点。由此可以联想到以1、2、3、4四个数字结尾的数保证能被7整除。这样不论前边的数怎样排列，后边四个数总有一种组合能够保证整体可以被7整除。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int z[7]={4123,1324,1234,2341,1243,3421,3142};
char s[23];
int ns[23];
int num0_9[10];
int atoi(char s)
{
return s-'0';
}
int fun(int x,int num)//把前边的数排列成新数
{
for(int i=0;i<num0_9[num];i++)
{
ns[x+i]=num;
}
return x+num0_9[num];
}
int fun2(int x)//求前边的数除以7的余数
{
int yu=0;
for(int i=0;i<x;i++)
{
yu=(yu*10+ns[i])%7;
}
return yu;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(num0_9,0,sizeof(num0_9));
scanf("%s",s);
int slen=strlen(s);
//统计每个数的个数
for(int i=0;i<slen;i++)
{
int num=atoi(s[i]);
num0_9[num]++;
}
//减去1、2、3、4
for(int i=1;i<=4;i++)
{
num0_9[i]--;
}
//求前边组成的新数
int x=0;
for(int i=1;i<=9;i++)
{
x=fun(x,i);
}
int yu=fun2(x);//求新数除以7的余数
int i;
//找到一种组合可以与前边的数组合起来被7整除
for(i=0;i<7;i++)
{
if((yu*10000+z[i])%7==0)
{
break;
}
}
//输出，后边可以补上0
for(int j=0;j<x;j++)
printf("%d",ns[j]);
printf("%d",z[i]);
for(int j=0;j<num0_9[0];j++)
printf("0");
printf("\n");
}
return 0;
}