1095. Nikifor 3

Time limit: 1.0 second

Memory limit: 64 MB

Nikifor knows that a certain positive integer has in its decimal form each of the digits 1,2,3,4. You are asked to determine if Nikifor can rearrange the digits of the number in such a way that the new number divides by 7.

Input

The first line contains the number 

N (not exceeding 10000) of positive integers that are to be checked. The next 

N lines contain these integers. Each number has no more than 20 digits.

Output

For each of the 

N numbers output a number divisible by 7 that can be obtained from the corresponding number from the input data by a rearrangement of the digits. If such rearrangement does not exist you should output 0 in the corresponding line. In the case of several valid rearrangements you may find only one of them.

Sample

input	output
21234531234	4123354123

Problem Author: Dmitry Filimonenkov

Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session

Tags: none  

(

)

Difficulty: 472              

         

 

思路：

 

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int ssss[7]={4123,1324,1234,2341,1243,3421,3142};

char str[22];

int num[10];

int length;

int map[20];

int sum,flag,t;

long long int frontpart,pppp;

int main()

{

scanf("%d",&t);

while(t --)

{

memset(str,0,sizeof(str));

memset(map,0,sizeof(map));

memset(num,0,sizeof(num));

scanf("%s",str);length = strlen(str);

for(int i = 0;i < length;i ++)

num[str[i] - 48] ++;

num[1] --;num[2] --;num[3] --;num[4] --;

frontpart = 0;

pppp = 1;

int k = 1;

for(int i = 1;i <= 9;i ++)

{

while(num[i] >= 1)

{

frontpart = frontpart * 10 + i;

map[k ++] = i;

num[i] --;

}

}

k --;

//printf("%lld\n",frontpart);

frontpart %= 7;

int i;

for(i = 0;i < 7;i ++)

{

if((frontpart * 10000 + ssss[i]) % 7 == 0)

break;

}

for(int l = 1;l <= k;l ++)

printf("%d",map[l]);

printf("%d",ssss[i]);

while(num[0] >= 1){

printf("0");num[0] --;}

printf("\n");

}

return 0;

}