Description

你需要给一批商品编号, 其中每个编号都是一个 7 位 16 进制数 (由 0~ 9, a-f 组成). 为了 防止在人工处理时不小心把编号弄错, 要求任意两个编号至少有三个位置对应的数字不相同. 第一个编号为 0000000, 第二个编号为不违反上述规定的前提下最小的编号,. ...... , 每次分配一个新编号时, 总是选择不和前面编号冲突的最小编号 (注意编号都是 16 进制数, 可以比较大小). 按此规律, 前面若干编号分别是:0000000, 0000111, 0000222, ..., 0000fff, 0001012, 0001103, 0001230, 0001321, 0001456, ...

输入 k, 你的任务是求出第 k 小的编号.

Input

第一行为整数 k.

Output

输出第 k 小的编号 (字母必须输出小写). 输入保证这个编号存在.

Sample Input

20

Sample Output

0001321

Data Range

编号 1-3 4-7 8-10
k \(\leq 200\) \(\leq 10000\) \(\leq 200000\)

Solution

发现又是一道恶心高维 dp...... 下方题解粘自 http://blog.csdn.net/sunshinezff/article/details/51216959

可以发现其实只需要保存 5 个位置.

因为至少有两个位置的数不同, 如果这两个位置不同, 那至少有三个位置不同.

从 7 个数中选 5 个数的方案有 21 种.

设 \(dp[x][a][b][c][d][e]\) 表示第 x 种排列 5 个数分别是 \(a, b, c, d, e\);

暴力枚举即可.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 16, maxm = 24;

int n, res; // That means a lot of memory...
bool dp_arr[maxm][maxn][maxn][maxn][maxn][maxn];
#define dp(_1,_2,_3,_4,_5,_6) dp_arr[_1][_2][_3][_4][_5][_6]

void print_hex(int a, int b, int c, int d, int e, int f, int g) {
    #define print_hex_s(__x) if(__x<10)printf("%d",__x);else printf("%c",__x-10+'a')
    // #define print_hex_s(__x) printf("%d ", __x);
    print_hex_s(a); print_hex_s(b); print_hex_s(c); print_hex_s(d);
    print_hex_s(e); print_hex_s(f); print_hex_s(g);
    printf("\n"); return ; }

#define forhex(__x) for(int __x=0;__x<=15;__x++)
#define breakall a=16;b=16;c=16;d=16;e=16;f=16;g=16

int main(int argc, char** argv)
{
    scanf("%d", &n);
    res = 0;
    forhex(a) forhex(b) forhex(c) forhex(d) forhex(e) forhex(f) forhex(g) {
        // print_hex(a, b, c, d, e, f, g);
        if (!dp(1, c, d, e, f, g)  && !dp(2, b, d, e, f, g)  &&
            !dp(3, b, c, e, f, g)  && !dp(4, b, c, d, f, g)  &&
            !dp(5, b, c, d, e, g)  && !dp(6, b, c, d, e, f)  &&
            !dp(7, a, d, e, f, g)  && !dp(8, a, c, e, f, g)  &&
            !dp(9, a, c, d, f, g)  && !dp(10, a, c, d, e, g) &&
            !dp(11, a, c, d, e, f) && !dp(12, a, b, e, f, g) &&
            !dp(13, a, b, d, f, g) && !dp(14, a, b, d, e, g) &&
            !dp(15, a, b, d, e, f) && !dp(16, a, b, c, f, g) &&
            !dp(17, a, b, c, e, g) && !dp(18, a, b, c, e, f) &&
            !dp(19, a, b, c, d, g) && !dp(20, a, b, c, d, f) &&
            !dp(21, a, b, c, d, e)) {
            res++;
            if (res >= n) {
                print_hex(a, b, c, d, e, f, g);
                breakall;
            }
            dp(1, c, d, e, f, g)  = true; dp(2, b, d, e, f, g)  = true;
            dp(3, b, c, e, f, g)  = true; dp(4, b, c, d, f, g)  = true;
            dp(5, b, c, d, e, g)  = true; dp(6, b, c, d, e, f)  = true;
            dp(7, a, d, e, f, g)  = true; dp(8, a, c, e, f, g)  = true;
            dp(9, a, c, d, f, g)  = true; dp(10, a, c, d, e, g) = true;
            dp(11, a, c, d, e, f) = true; dp(12, a, b, e, f, g) = true;
            dp(13, a, b, d, f, g) = true; dp(14, a, b, d, e, g) = true;
            dp(15, a, b, d, e, f) = true; dp(16, a, b, c, f, g) = true;
            dp(17, a, b, c, e, g) = true; dp(18, a, b, c, e, f) = true;
            dp(19, a, b, c, d, g) = true; dp(20, a, b, c, d, f) = true;
            dp(21, a, b, c, d, e) = true;
        }
    }
    return 0;
}