已知,a1,a2,…,an 是 1∼n 的全排列中字典序第 k 个排列。 请你判断,一共有多少个整数 x 同时满足以下所有条件: 1≤x≤n x 的十进制表示不含 4 和 7 以外的数字。 ax 的十进制表示不含 4 和 7 以外的数字。 输入格式 共一行,包含两个整数 n,k 。 输出格式 如果 1∼n 的全排列中字典序第 k 个排列根本不存在,则输出 -1。 否则,输出一个整数,表示满足条件的 x 的数量。 数据范围 前 4 个测试点满足 1≤n,k≤10 。 所有测试点满足 1≤n,k≤109 。 输入样例1: 7 4 输出样例1: 1 输入样例2: 4 7 输出样例2: 1 输入样例3: 3 7 输出样例3: -1
时间: 2024-04-16 20:28:47 浏览: 132
按字典顺序排列的第 k 个排列:此函数返回按字典顺序排列的第 k 个排列。-matlab开发
首先,我们需要找到第 k 个排列。可以使用递归的方式来生成全排列,并且在生成过程中判断是否达到第 k 个排列。
接下来,我们需要判断满足条件的 x 的数量。根据题目描述,数字 x 和 ax 的十进制表示都不能包含除了 4 和 7 以外的数字。我们可以遍历 1 到 n 的每个数字,将其转换为十进制表示,然后判断是否满足条件。对于每个数字 x,我们还需要判断其对应的 ax 是否满足条件。
下面是实现这个算法的伪代码:
```
count = 0
for x in range(1, n+1):
if contains_other_digits(x) and contains_other_digits(a[x]):
count += 1
if count > 0:
print(count)
else:
print(-1)
```
其中,contains_other_digits(x) 是一个函数,用于判断数字 x 的十进制表示是否包含除了 4 和 7 以外的其他数字。
接下来,我们可以将以上伪代码转化为具体的代码实现。以下是一个可能的实现方式:
```python
def contains_other_digits(num):
digits = str(num)
for digit in digits:
if digit != '4' and digit != '7':
return False
return True
def find_kth_permutation(n, k):
# 生成全排列
def generate_permutation(arr, start):
if start == len(arr):
nonlocal count
count += 1
if count == k:
return arr
for i in range(start, len(arr)):
arr[start], arr[i] = arr[i], arr[start]
generate_permutation(arr, start + 1)
arr[start], arr[i] = arr[i], arr[start]
arr = list(range(1, n+1))
count = 0
permutation = generate_permutation(arr, 0)
return permutation
def count_satisfying_numbers(n, k):
permutation = find_kth_permutation(n, k)
count = 0
for x in range(1, n+1):
if contains_other_digits(x) and contains_other_digits(permutation[x-1]):
count += 1
return count
n, k = map(int, input().split())
count = count_satisfying_numbers(n, k)
if count > 0:
print(count)
else:
print(-1)
```
这样,我们就可以根据给定的 n 和 k 找到第 k 个排列,并计算满足条件的 x 的数量。如果满足条件的数量大于 0,则输出该数量,否则输出 -1。
阅读全文