AlgoMooc
← 返回题库

P3810. 数字排列

中等通过率 36% · 提交 513 · 通过 184
回溯DFS排序数学

小慕在筹备团队的年会活动,设计了一个趣味游戏: 屏幕上会显示 1 到 9 中任意 4 个不重复的数字,参与者需要尽快找出这些数字能拼成的所有数字中,从小到大排列位于第 N 位的那个数字,其中 N 等于屏幕上给出的数字中最大的那个(如果拼出的数字总数不到 N 个,则取最后一个数字即可)。 注意: - 数字 进行数字拼接,且屏幕上不会同时出现 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,4

输出

-1

说明:2和5不能同时出现

示例 3

输入

3,0,9,5

输出

-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

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。