Posted on 2012-03-01 13:50
C小加 閱讀(266)
評論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告
題目保證至少有一個(gè)1、2、3、4。說明這四個(gè)數(shù)是一個(gè)突破點(diǎn)。由此可以聯(lián)想到以1、2、3、4四個(gè)數(shù)字結(jié)尾的數(shù)保證能被7整除。這樣不論前邊的數(shù)怎樣排列，后邊四個(gè)數(shù)總有一種組合能夠保證整體可以被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)//把前邊的數(shù)排列成新數(shù)
{
for(int i=0;i<num0_9[num];i++)
{
ns[x+i]=num;
}
return x+num0_9[num];
}
int fun2(int x)//求前邊的數(shù)除以7的余數(shù)
{
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);
//統(tǒng)計(jì)每個(gè)數(shù)的個(gè)數(shù)
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]--;
}
//求前邊組成的新數(shù)
int x=0;
for(int i=1;i<=9;i++)
{
x=fun(x,i);
}
int yu=fun2(x);//求新數(shù)除以7的余數(shù)
int i;
//找到一種組合可以與前邊的數(shù)組合起來被7整除
for(i=0;i<7;i++)
{
if((yu*10000+z[i])%7==0)
{
break;
}
}
//輸出，后邊可以補(bǔ)上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;
}