出题人题解 | #tokitsukaze and Number Game#

原题解链接：https://ac.nowcoder.com/discuss/150249

首先一个结论:若后三位能被8整除，那么这个数就能被8整除。

那么做法就是贪心，前面的数尽量大，后三位的每位都尽量小，而且排列后能被$88$整除。

实现方式比较多(? ), 这里仅说一下$stdstd$做法。

特判掉只有$11$位和$22$位，这里注意不能直接判能不能被$88$整除，比如$23->3223->32$。

预处理后$33$位能被$88$整除的所有情况，每种情况按字典序降序后，再总体按字典序升序。

比如: $104->410104->410$， $112->211112->211$。 字典序。

然后数数每个数字的个数。从小到大(指的是字典序)枚举预处理的3位数，看看数字够不够拼，够就用这$33$位当末尾的$33$位。(都不够就是$-1-1$了)

然后把这3位取出来。其他的数从大到小$sortsort$。这$33$位做个全排列，取个最大能被$88$整除的数，拼起来就是答案。

//
// Created by calabash_boy on 18-10-18.
//
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#ifdef __LOCAL_DEBUG__
# define _debug(fmt, ...) fprintf(stderr, "\033[91m[%s %3d]: " fmt "\n\033[0m", \
  __func__,__LINE__, ##__VA_ARGS__)
#else
# define _debug(...) (void(0))
#endif

#define PB(x) push_back(x)
#define rep(i,l,r) for (int i = l,_ = r;i< _;i++)
#define REP(i,l,r) for (int i=l,_=r;i<=_;i++)
#define leave(x) do {cout<<#x<<endl;fflush(stdout);return 0;}while (0);
#define untie do{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}while (0)

typedef long long LL;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 0x3f3f3f3f;
const ll inf_ll = 0x3f3f3f3f3f3f3f3fLL;


/************* header ******************/
set<int> pattern = {0,
                    8,
                    16,
                    24,
                    32,
                    40,
                    48,
                    56,
                    64,
                    72,
                    80,
                    88,
                    96,
                    104,
                    112,
                    120,
                    128,
                    136,
                    144,
                    152,
                    160,
                    168,
                    176,
                    184,
                    192,
                    200,
                    208,
                    216,
                    224,
                    232,
                    240,
                    248,
                    256,
                    264,
                    272,
                    280,
                    288,
                    296,
                    304,
                    312,
                    320,
                    328,
                    336,
                    344,
                    352,
                    360,
                    368,
                    376,
                    384,
                    392,
                    400,
                    408,
                    416,
                    424,
                    432,
                    440,
                    448,
                    456,
                    464,
                    472,
                    480,
                    488,
                    496,
                    504,
                    512,
                    520,
                    528,
                    536,
                    544,
                    552,
                    560,
                    568,
                    576,
                    584,
                    592,
                    600,
                    608,
                    616,
                    624,
                    632,
                    640,
                    648,
                    656,
                    664,
                    672,
                    680,
                    688,
                    696,
                    704,
                    712,
                    720,
                    728,
                    736,
                    744,
                    752,
                    760,
                    768,
                    776,
                    784,
                    792,
                    800,
                    808,
                    816,
                    824,
                    832,
                    840,
                    848,
                    856,
                    864,
                    872,
                    880,
                    888,
                    896,
                    904,
                    912,
                    920,
                    928,
                    936,
                    944,
                    952,
                    960,
                    968,
                    976,
                    984,
                    992
};
const int maxn = 150;
char s[maxn],t[maxn];
char ans[maxn];
int cnt[10];
int Cnt[10];
int main(){
    int T;
    for (scanf("%d",&T);T;T--){
        scanf("%s",s);
        memset(t,0,sizeof t);
        int n = strlen(s);
        if (n == 1){
            if (s[0] == '0' || s[0] == '8'){
                puts(s);
            }else{
                puts("-1");
            }
        }else if (n == 2) {
            int x;
            sscanf(s,"%d",&x);
            int dig1 = x/10;
            int dig2 = x%10;
            int y = dig2*10 + dig1;
            int ans = -1;
            if (x %8 == 0)ans = x;
            if (y > 10 && y%8 == 0 ) {
                ans = max(ans,y);
            }
            printf("%d\n",ans);
        }else if (n == 3) {
            int x;
            sscanf(s,"%d",&x);
            int dig1 = x%10;
            int dig2 = (x/10 )%10;
            int dig3 = x/100;
            int ans =-1;
            for (int i=0;i<3;i++)for (int j=0;j<3;j++){
                if (i == j)continue;
                int k = 0+1+2 - i - j;
                t[i] = dig1+'0';
                t[j] = dig2+'0';
                t[k] = dig3+'0';
                int y;
                sscanf(t,"%d",&y);
                if (y >=100 && y%8 == 0){
                    ans = max(ans,y);
                }
            }
            printf("%d\n",ans);
        }else{
                memset(cnt,0,sizeof cnt);
                memset(ans,0,sizeof ans);
                for (int i=0;i<n;i++){
                    cnt[s[i] - '0']++;
                }
                for (int x: pattern){
                    int dig1 = x%10;
                    int dig2 = (x/10 )%10;
                    int dig3 = x/100;
                    memcpy(Cnt,cnt,sizeof cnt);
                    Cnt[dig1]--;Cnt[dig2]--;Cnt[dig3] --;
                    if (Cnt[dig1]>=0 && Cnt[dig2]>=0 && Cnt[dig3]>=0){

                        t[n-1] = dig1+'0';
                        t[n-2] = dig2+'0';
                        t[n-3] = dig3+'0';
                        for (int now = n-4,i=0;i<=9;i++){
                            while (Cnt[i])t[now--] = i+'0',Cnt[i] --;
                        }
                        t[n] = '\0';
                        if (t[0] != '0' && strcmp(ans,t)<0){
                            memcpy(ans,t,sizeof t);
                        }
                    }
                }
                if (ans[0] == '\0'){
                    puts("-1");
                }else{
                    puts(ans);
                }
            }
    }
    return 0;
}