网站开发环境有哪些,企业软件项目管理系统,wordpress 代码高亮中文,wordpress实现预览#x1f36d; 大家好这里是清隆学长 #xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 #x1f4bb; ACM银牌#x1f948;| 多次AK大厂笔试 #xff5c; 编程一对一辅导 #x1f44f; 感谢大家的订阅➕ 和 喜欢#x1f497; #x1f… 大家好这里是清隆学长 一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 ACM银牌| 多次AK大厂笔试 编程一对一辅导 感谢大家的订阅➕ 和 喜欢 在线评测链接
https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1086 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁
OJ题目截图 文章目录 在线评测链接OJ题目截图 数字排列游戏问题描述输入格式输出格式样例输入样例一样例二样例三样例四 样例输出样例一样例二样例三样例四 样例解释样例一样例二样例三样例四 数据范围题解参考代码 数字排列游戏
问题描述
K 小姐负责公司年会想出一个趣味游戏屏幕给出 1 − 9 1-9 1−9 中任意 4 4 4 个不重复的数字大家需要以最快时间给出这几个数字可拼成的数字从小到大排列位于第 n n n 位置的数字其中 n n n 为给出数字中最大的。如果不到这么多数字则给出最后一个即可。
注意 2 2 2 可以当作 5 5 5 来使用 5 5 5 也可以当作 2 2 2 来使用进行数字拼接且屏幕不能同时给出 2 2 2 和 5 5 5。 6 6 6 可以当作 9 9 9 来使用 9 9 9 也可以当作 6 6 6 来使用进行数字拼接且屏幕不能同时给出 6 6 6 和 9 9 9。
例如给出的数字 1 1 1, 4 4 4, 8 8 8, 7 7 7 则可以拼接的数字为 1 1 1, 4 4 4, 7 7 7, 8 8 8, 14 14 14, 17 17 17, 18 18 18, 41 41 41, 47 47 47, 48 48 48, 71 71 71, 74 74 74, 78 78 78, 81 81 81, 84 84 84, 87 87 87, 147 147 147, 148 148 148, 178 178 178…省略后面的数字。因此第 n n n即 8 8 8个数字为 41 41 41。
输入格式
输入以逗号分隔的 4 4 4 个 i n t int int 类型整数的字符串。
输出格式
输出为这几个数字可拼成的数字从小到大排列位于第 n n n n n n 为输入数字中最大的数字位置的数字。如果输入的数字不在范围内或者有重复则输出 − 1 -1 −1。
样例输入
样例一
1,4,8,7样例二
2,5,1,4样例三
3,0,9,1样例四
3,9,7,8样例输出
样例一
41样例二
-1样例三
-1样例四
39样例解释
样例一
可以构成的数字按从小到大排序为 1 1 1, 4 4 4, 7 7 7, 8 8 8, 14 14 14, 17 17 17, 18 18 18, 41 41 41, 47 47 47, 48 48 48, 71 71 71, 74 74 74, 78 78 78, 81 81 81, 84 84 84, 87 87 87, 147 147 147, 148 148 148, 178 178 178…省略后面的数字故第 8 8 8 个数字为 41 41 41。
样例二 2 2 2 和 5 5 5 不能同时出现。
样例三 0 0 0 不在 1 1 1 到 9 9 9 的范围内。
样例四
注意 9 9 9 可以当 6 6 6 使用所以可以构成的数字按从小到大排序为 3 3 3, 6 6 6, 7 7 7, 8 8 8, 9 9 9, 36 36 36, 37 37 37, 38 38 38, 39 39 39, 63 63 63, 67 67 67, 68 68 68, 73 73 73, 76 76 76, 78 78 78, 79 79 79, 83 83 83 … (省略后面的数字)故第 9 9 9 个为 39 39 39。
数据范围
输入的数字范围为 1 − 9 1-9 1−9且不重复。
题解
这道题的关键在于处理数字的排列组合并且考虑到 2 2 2 和 5 5 5 以及 6 6 6 和 9 9 9 的互换使用。我们需要生成所有可能的数字组合然后进行排序最后根据最大数字的位置输出相应的结果。
参考代码
Python
def main():import sysinput sys.stdin.readw list(map(int, input().strip().split(,)))w.sort()st set(w)k max(w)dic {2: 5, 5: 2, 6: 9, 9: 6}vis [False] * 4res []def dfs(u, num, cnt):if u cnt:res.append(num)returnfor i in range(4):if vis[i]:continuevis[i] Truedfs(u 1, num * 10 w[i], cnt)if w[i] in dic:dfs(u 1, num * 10 dic[w[i]], cnt)vis[i] Falseif 0 in st or (2 in st and 5 in st) or (6 in st and 9 in st):print(-1)else:for i in range(1, 5):dfs(0, 0, i)res.sort()if k len(res):print(res[-1])else:print(res[k - 1])if __name__ __main__:main()Java
import java.util.*;public class Main {private static int[] w;private static boolean[] vis;private static ListInteger res new ArrayList();private static MapInteger, Integer dic Map.of(2, 5, 5, 2, 6, 9, 9, 6);private static void dfs(int u, int num, int cnt) {if (u cnt) {res.add(num);return;}for (int i 0; i 4; i) {if (vis[i]) continue;vis[i] true;dfs(u 1, num * 10 w[i], cnt);if (dic.containsKey(w[i])) {dfs(u 1, num * 10 dic.get(w[i]), cnt);}vis[i] false;}}public static void main(String[] args) {Scanner scanner new Scanner(System.in);String[] input scanner.nextLine().trim().split(,);w Arrays.stream(input).mapToInt(Integer::parseInt).toArray();Arrays.sort(w);SetInteger st new HashSet();for (int num : w) {st.add(num);}vis new boolean[4];int k w[w.length - 1];if (st.contains(0) || (st.contains(2) st.contains(5)) || (st.contains(6) st.contains(9))) {System.out.println(-1);} else {for (int i 1; i 4; i) {dfs(0, 0, i);}Collections.sort(res);if (k res.size()) {System.out.println(res.get(res.size() - 1));} else {System.out.println(res.get(k - 1));}}}
} Cpp
#include bits/stdc.husing namespace std;vectorint w;
bool vis[4];
vectorint res;
unordered_mapint, int dic {{2, 5}, {5, 2}, {6, 9}, {9, 6}};void dfs(int u, int num, int cnt) {if (u cnt) {res.push_back(num);return;}for (int i 0; i 4; i) {if (vis[i]) continue;vis[i] true;dfs(u 1, num * 10 w[i], cnt);if (dic.count(w[i])) {dfs(u 1, num * 10 dic[w[i]], cnt);}vis[i] false;}
}int main() {string input;getline(cin, input);replace(input.begin(), input.end(), ,, );stringstream ss(input);int num;while (ss num) {w.push_back(num);}sort(w.begin(), w.end());unordered_setint st(w.begin(), w.end());int k w[w.size() - 1];if (st.count(0) || (st.count(2) st.count(5)) || (st.count(6) st.count(9))) {cout -1 endl;} else {for (int i 1; i 4; i) {dfs(0, 0, i);}sort(res.begin(), res.end());if (k res.size()) {cout res.back() endl;} else {cout res[k - 1] endl;}}return 0;
}
