CS Academy 8 Divisible

题目链接：https://csacademy.com/contest/archive/task/8-divisible

题目大意：给出一个大数N，长度不超过1000位。现在要求将N的所有位重新排列，使得其能够被8整除。输出最小的可能解，如果没有解，输出-1. 输出不允许有前导0。

解题思路：考虑1,10,100,1000……模8，发现分别是1,2,4,0,0……。也就是说从1000开始的10的幂都能够被8整除了。那么对于由an-1,an-2……a2,a0,a1组成的数字N来说，只需要考虑最后三位即可，确定最后三位之后判断其是否为一个可行解，记录下了，最后取最小可行解或者输出-1。

大致过程：记录下N中每位每个数字出现的次数；然后从992开始每次减8枚举所有能够被8整除的3,2,1位数xi，对于每个数字xi，判断其个十百三位是否可得到，以及结果是否含有前导0；全部记录下来最后输出字典序最小即可。

代码：

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <queue>
 7 #include <vector>
 8 #include <string>
 9 using namespace std;
10 const int maxn = 1e3 + 5;
11 char str[maxn];
12 int tis[10], len = 0;
13 string ans;
14 
15 void doout(int a, int b, int c){
16     int tps[10];
17     memcpy(tps, tis, sizeof(tis));
18     tps[a] -= 1; tps[b] -= 1; tps[c] -= 1;
19     string tmp;
20     for(int i = 1; i < 10; i++){
21         if(tps[i] > 0){
22             tmp.push_back(i + '0');
23             tps[i] -= 1;
24             break;
25         }
26     }
27     for(int i = 0; i < 10; i++){
28         if(tps[i] > 0){
29             for(int j = 0; j < tps[i]; j++)
30                 tmp.push_back(i + '0');
31         }
32     }
33     tmp.push_back(a + '0');
34     tmp.push_back(b + '0');
35     tmp.push_back(c + '0');
36     if(ans.size() == 0 || tmp < ans) ans = tmp;
37 }
38 bool check(int a, int b, int c){
39     int tps[10];
40     memcpy(tps, tis, sizeof(tps));
41     tps[a] -= 1; tps[b] -= 1; tps[c] -= 1;
42     for(int i = 0; i < 10; i++) if(tps[i] < 0) return false;
43     bool has3 = false;
44     for(int i = 1; i < 10; i++) if(tps[i] > 0) has3 = true;
45     if(has3 || (len == 3 && a != 0)) {
46         doout(a, b, c);
47         return true;
48     }
49     else return false;
50 }
51 void solve(){
52     len = strlen(str);
53     if(len == 1){
54         int u = str[0] - '0';
55         if(u % 8 == 0) puts(str);
56         else puts("-1");
57         return;
58     }
59     else if(len == 2){
60         int u = str[0] - '0', v = str[1] - '0';
61         if(u > v) swap(u, v);
62         if((u * 10 + v) % 8 == 0 && u != 0) printf("%d%d
", u, v);
63         else if((v * 10 + u) % 8 == 0 && v != 0) printf("%d%d
", v, u);
64         else puts("-1");
65         return;
66     }
67     else{
68         bool flag = false;
69         memset(tis, 0, sizeof(tis));
70         for(int i = 0; str[i]; i++) tis[str[i] - '0']++;
71         for(int i = 992; i >= 0; i -= 8){
72             int x = i, a, b, c;
73             a = x / 100; x %= 100;
74             b = x / 10; x %= 10;
75             c = x;
76             if(check(a, b, c)) flag = true;
77         }
78         if(!flag) puts("-1");
79         else{
80             for(int i = 0; i < (int)ans.size(); i++)
81                 str[i] = (char) ans[i];
82             str[ans.size()] = 0;
83             puts(str);
84         }
85     }
86 }
87 int main(){
88     scanf("%s", str);
89     solve();
90     return 0;
91 }

题目：

8 Divisible

Time limit: 1000 ms
Memory limit: 256 MB

You are given a large number

If the solution is not unique, print the smallest one. Leading

Standard input

The first line contains a single large number

Standard output

If there is no solution output

Otherwise, print the answer on the first line.

Constraints and notes

The number of digits of $1\,0001000$

Input	Output	Explanation
625	256
173	-1	There is no permutation of digits that creates a number divisible by
2048	2048