C. Divisible by Seven

C. Divisible by Seven time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

You have number a, whose decimal representation quite luckily contains digits 1, 6, 8, 9. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7.

Number a doesn't contain any leading zeroes and contains digits 1, 6, 8, 9 (it also can contain another digits). The resulting number also mustn't contain any leading zeroes.

Input

The first line contains positive integer a in the decimal record. It is guaranteed that the record of number a contains digits: 1, 6, 8, 9. Number a doesn't contain any leading zeroes. The decimal representation of number a contains at least 4 and at most 10⁶ characters.

Output

Print a number in the decimal notation without leading zeroes — the result of the permutation.

If it is impossible to rearrange the digits of the number a in the required manner, print 0.

Examples Input 1689 Output 1869 Input 18906 Output 18690

题解：题目中告诉我们给出的字符串必须包含1 6 8 9这四个数字，我们对这四个数字进行排列组合不难发现，其排列结果对7取余的结果包含0,1,2,3,4,5,6。要想字符串可以整除7，只需把字符串分成1 6 8 9 和剩下的两部分并且让他们的结果可以对7整除。分为两种情况，一种是除了1 6 8 9之外都是零，这样只需把1 6 8 9 放在前面即可；第二种为除了1 6 8 9 外，字符串还有其他非零数字，这种用剩下的先对7取余，然后如果不能整除再用1 6 8 9 补齐即可……

#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<stdlib.h> #include<time.h> #include<math.h> #include<queue>; #include<stack>; using namespace std; char f[8][5]={"1869","1968","1689","6198","1698","1986","1896"}; //1689 对7取余结果分别为0 1 2 3 4 5 6的几种排列 char x[1000005]; // 储存字符串 int y[1000005],v[10]; // V数组标记1 6 8 9； int main() { scanf("%s",x); memset(v,0,sizeof(v)); int len=strlen(x); for(int i=0;i<strlen(x);i++) { y[i]=x[i]-'0'; if(y[i]==1&&!v[1]) { y[i]=0;v[1]=1; } if(y[i]==6&&!v[6]) { y[i]=0;v[6]=1; } if(y[i]==8&&!v[8]) { y[i]=0;v[8]=1; } if(y[i]==9&&!v[9]) { y[i]=0;v[9]=1; } } sort(y,y+strlen(x)); int ant=0; for(int i=len-1;i>=0;i--) { ant=ant*10+y[i]; ant%=7; } if(y[len-1]==0) // 情况一 { printf("%s",f[(7-ant)%7]); for(int i=0;i<len-4;i++) printf("0"); printf("\n"); } else // 情况二 { for(int i=len-1;i>=4;i--) printf("%d",y[i]); printf("%s\n",f[(7-ant)%7]); } }