题目描述

小明负责公司年会，设计了一个趣味游戏：

屏幕给出 $1$ ~ $9$ 中任意 $4$ 个不重复的数字，大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第 $N$ 位置的数字，其中 $N$ 为给出数字中最大的（如果不到这么多数字则给出最后一个即可）。

注意：

• $2$ 可以当作 $5$ 来使用，$5$ 也可以当作 $2$ 来使用进行数字拼接，且屏幕不能同时给出 $2$ 和 $5$；
• $6$ 可以当作 $9$ 来使用，$9$ 也可以当作 $6$ 来使用进行数字拼接，且屏幕不能同时给出 $6$ 和 $9$。

如果输入的数字不在范围内或者有重复，则输出 $-1$。

思路

1. 输入验证：首先读取输入，并进行基本验证：

   • 检查数字是否在 $1$ 到 $9$ 之间。
   • 检查是否有重复数字。
   • 检查是否同时包含 $2$ 和 $5$，或同时包含 $6$ 和 $9$。

2. 生成可能的数字列表：

   • 对于每个输入的数字，根据规则生成它可能表示的数字。例如，$2$ 可以表示为 $2$ 和 $5$。
   • 将所有可能的数字加入到一个集合中，以避免重复。

3. 生成所有排列组合：

   • 使用回溯算法生成所有长度为 $1$ 到 $n$ 的可能数字排列，注意在每个数字中不重复使用相同的数字。
   • 将生成的数字转换为整数，并加入到结果集合中。

4. 排序并输出结果：

   • 将结果集合转换为有序列表。
   • 根据输入数字中的最大值 $N$，输出第 $N$ 个数字，如果总数少于 $N$，则输出最后一个数字。

cpp

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>
using namespace std;

// 递归函数，生成所有可能的数字组合
void backtrack(int index, vector<vector<char>>& representations, vector<char>& current, set<int>& results) {
    // 生成当前组合的所有排列
    if (!current.empty()) {
        // 生成所有排列
        // 使用 next_permutation 需要先对当前组合进行排序
        vector<char> sorted_current = current;
        sort(sorted_current.begin(), sorted_current.end());
        do {
            string num_str(sorted_current.begin(), sorted_current.end());
            results.insert(stoi(num_str));
        } while (next_permutation(sorted_current.begin(), sorted_current.end()));
    }

    for (int i = index; i < representations.size(); ++i) {
        for (char digit : representations[i]) {
            current.push_back(digit);
            backtrack(i + 1, representations, current, results);
            current.pop_back();
        }
    }
}

int main() {
    string input;
    getline(cin, input);

    // 分割输入字符串，获取数字
    stringstream ss(input);
    string token;
    vector<int> nums;
    set<int> numSet; // 用于检查重复
    int maxNum = INT_MIN; // 记录最大数字

    while (getline(ss, token, ',')) {
        // 去除可能的空格
        token.erase(remove_if(token.begin(), token.end(), ::isspace), token.end());
        if (token.empty()) {
            cout << "-1" << endl;
            return 0;
        }
        int num;
        try {
            num = stoi(token);
        } catch (...) {
            cout << "-1" << endl;
            return 0;
        }
        if (num < 1 || num > 9) {
            cout << "-1" << endl;
            return 0;
        }
        if (numSet.count(num)) {
            cout << "-1" << endl;
            return 0;
        }
        nums.push_back(num);
        numSet.insert(num);
        maxNum = max(maxNum, num);
    }

    // 输入必须有4个数字
    if (nums.size() != 4) {
        cout << "-1" << endl;
        return 0;
    }

    // 检查是否同时包含2和5，6和9
    if ((numSet.count(2) && numSet.count(5)) || (numSet.count(6) && numSet.count(9))) {
        cout << "-1" << endl;
        return 0;
    }

    // 为每个数字生成可能的表示
    vector<vector<char>> representations;
    for (int num : nums) {
        vector<char> reps;
        if (num == 2 || num == 5) {
            reps.push_back('2');
            reps.push_back('5');
        } else if (num == 6 || num == 9) {
            reps.push_back('6');
            reps.push_back('9');
        } else {
            reps.push_back('0' + num);
        }
        representations.push_back(reps);
    }

    set<int> results;
    vector<char> current;
    backtrack(0, representations, current, results);

    // 将结果转换为有序列表
    vector<int> resultList(results.begin(), results.end());
    sort(resultList.begin(), resultList.end());

    // 输出第N个数字
    int N = maxNum;
    if (N > resultList.size()) {
        N = resultList.size();
    }
    if (N <= 0) {
        cout << "-1" << endl;
    } else {
        cout << resultList[N - 1] << endl;
    }

    return 0;
}

python

import sys
import itertools

def main():
    # 读取输入并去除首尾空白字符
    input_str = sys.stdin.readline().strip()
    tokens = input_str.split(',')

    nums = []
    num_set = set()
    max_num = -float('inf')

    # 输入验证
    for token in tokens:
        token = token.strip()
        if not token:
            print(-1)
            return
        try:
            num = int(token)
        except:
            print(-1)
            return
        if num < 1 or num > 9:
            print(-1)
            return
        if num in num_set:
            print(-1)
            return
        nums.append(num)
        num_set.add(num)
        if num > max_num:
            max_num = num

    # 输入必须有4个数字
    if len(nums) != 4:
        print(-1)
        return

    # 检查是否同时包含2和5，或者6和9
    if (2 in num_set and 5 in num_set) or (6 in num_set and 9 in num_set):
        print(-1)
        return

    # 为每个数字生成可能的表示
    representations = []
    for num in nums:
        reps = []
        if num == 2 or num == 5:
            reps = ['2', '5']
        elif num == 6 or num == 9:
            reps = ['6', '9']
        else:
            reps = [str(num)]
        representations.append(reps)

    results = set()

    # 递归生成所有可能的组合
    def backtrack(index, current):
        # 如果当前组合不为空，则生成所有排列并加入结果集
        if current:
            # 生成当前组合的所有排列
            perms = set(itertools.permutations(current))
            for perm in perms:
                num = int(''.join(perm))
                results.add(num)
        # 继续选择下一个数字
        for i in range(index, len(representations)):
            for rep in representations[i]:
                current.append(rep)
                backtrack(i + 1, current)
                current.pop()

    backtrack(0, [])

    # 将结果转换为有序列表
    result_list = sorted(results)

    # 输出第N个数字
    N = max_num
    if N > len(result_list):
        N = len(result_list)
    if N <= 0:
        print(-1)
    else:
        print(result_list[N - 1])

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    // 递归函数，生成所有可能的数字组合
    public static void backtrack(int index, List<List<Character>> representations, List<Character> current, Set<Integer> results) {
        if (!current.isEmpty()) {
            // 生成当前组合的所有排列
            List<Character> sortedCurrent = new ArrayList<>(current);
            Collections.sort(sortedCurrent);
            Set<String> perms = new HashSet<>();
            permute(sortedCurrent, 0, perms);
            for (String perm : perms) {
                results.add(Integer.parseInt(perm));
            }
        }

        for (int i = index; i < representations.size(); i++) {
            for (char digit : representations.get(i)) {
                current.add(digit);
                backtrack(i + 1, representations, current, results);
                current.remove(current.size() - 1);
            }
        }
    }

    // 生成所有排列并存储为字符串
    public static void permute(List<Character> chars, int start, Set<String> perms) {
        if (start == chars.size() - 1) {
            StringBuilder sb = new StringBuilder();
            for (char c : chars) {
                sb.append(c);
            }
            perms.add(sb.toString());
            return;
        }
        for (int i = start; i < chars.size(); i++) {
            Collections.swap(chars, start, i);
            permute(chars, start + 1, perms);
            Collections.swap(chars, start, i);
        }
    }

    public static void main(String[] args) throws IOException {
        // 读取输入并验证
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        String[] tokens = input.split(",");

        Set<Integer> numSet = new HashSet<>();
        int maxNum = Integer.MIN_VALUE;
        List<Integer> nums = new ArrayList<>();

        // 输入验证
        for (String token : tokens) {
            token = token.trim();
            if (token.isEmpty()) {
                System.out.println(-1);
                return;
            }
            int num;
            try {
                num = Integer.parseInt(token);
            } catch (NumberFormatException e) {
                System.out.println(-1);
                return;
            }
            if (num < 1 || num > 9) {
                System.out.println(-1);
                return;
            }
            if (numSet.contains(num)) {
                System.out.println(-1);
                return;
            }
            nums.add(num);
            numSet.add(num);
            if (num > maxNum) {
                maxNum = num;
            }
        }

        // 输入必须有4个数字
        if (nums.size() != 4) {
            System.out.println(-1);
            return;
        }

        // 检查是否同时包含2和5，6和9
        if ((numSet.contains(2) && numSet.contains(5)) || (numSet.contains(6) && numSet.contains(9))) {
            System.out.println(-1);
            return;
        }

        // 为每个数字生成可能的表示
        List<List<Character>> representations = new ArrayList<>();
        for (int num : nums) {
            List<Character> reps = new ArrayList<>();
            if (num == 2 || num == 5) {
                reps.add('2');
                reps.add('5');
            } else if (num == 6 || num == 9) {
                reps.add('6');
                reps.add('9');
            } else {
                reps.add((char) ('0' + num));
            }
            representations.add(reps);
        }

        Set<Integer> results = new HashSet<>();
        List<Character> current = new ArrayList<>();
        backtrack(0, representations, current, results);

        // 将结果转换为有序列表
        List<Integer> resultList = new ArrayList<>(results);
        Collections.sort(resultList);

        // 输出第N个数字
        int N = maxNum;
        if (N > resultList.size()) {
            N = resultList.size();
        }
        if (N <= 0) {
            System.out.println(-1);
        } else {
            System.out.println(resultList.get(N - 1));
        }
    }
}

题目内容

小明负责公司年会，想出一个趣味游戏：

屏幕给出 $1$ ~ $9$ 中任意 $4$ 个不重复的数字，大家以最快时间给出这几个数字可拼成的数字从小到大排列位于第 $N$ 位置的数字，其中 $N$ 为给出数字中最大的（如果不到这么多数字则给出最后一个即可）。

注意：

• $2$ 可以当作 $5$ 来使用，$5$ 也可以当作 $2$ 来使用进行数字拼接，且屏幕不能同时给出 $2$ 和 $5$；
• $6$ 可以当作 $9$ 来使用，$9$ 也可以当作 $6$ 来使用进行数字拼接，且屏幕不能同时给出 $6$ 和 $9$。

如给出：$1$，$4$，$8$，$7$，则可以拼接的数字为：

$1$，$4$，$7$，$8$，$14$，$17$，$18$，$41$，$47$，$48$，$71$，$74$，$78$，$81$，$84$，$87$，$147$，$148$，$178$ ... (省略后面的数字)

那么第 $N$ （即 $8$）个的数字为 $41$ 。

输入描述

输入以逗号分隔的 $4$ 个 $int$ 类型整数的字符串。

输出描述

输出为这几个数字可拼成的数字从小大大排列位于第 $N$ （ $N$ 为输入数字中最大的数字）位置的数字，

如果输入的数字不在范围内或者有重复，则输出 $-1$。

样例1

输入

1,4,8,7

输出

41

说明

可以构成的数字按从小到大排序为：

1，4，7，8，14，17，18，41，47，48，71，74，78，81，84，87，147，148，178 ... （省略后面的数字），

故第8个为41

样例2

输入

2,5,1

输出

-1

说明

2和5不能同时出现

样例3

输入

3,0,9

输出

-1

说明

0不在1到9范围内

样例4

输入

3,9,7,8

输出

39

说明

注意9可以当6使用，所以可以构成的数字按从小到大排序为：3，6，7，8，9，36，37，38，39，63，67，68，73，76，78，79，83 ... （省略后面的数字），

故第9个为39