工号不够用了怎么办？ - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷）最新题库【超值优惠】Java/Python/C++合集

华为od机试

题目描述

3020年，空间通信集团的员工人数数量突破20亿，现有工号系统不够用的窘境。

现在，请你负责调研新工号系统。继承历史传统，新工号系统由小写英文字母（a-z）和数字（0-9）两部分构成。

新工号分一段英文字符开头，之后跟着一段数字，例如"aaaahw0001"，"a12345"，"abcd1"，"a00"。

注意新工号数字不能全字母或者数字，允许数字部分有前导0或者全为0。

但是过长的工号会增加同事们的记忆成本，现给出新工号至少需要分配的人数X和新工号中字母的长度Y，求新工号中数字的最短长度Z。

输入描述

一行两个非负整数X和Y，代表字母单个字母空间总数。

0 <= X <= 2^50 - 1

0 < Y <= 5

输出描述

输出新工号中数字部分的最短长度。

示例1

输入：
260 1

输出：
1

示例2

输入：
26 1

输出：
1

说明：
数字长度不能为0

题解

这道题的目的是在给定新工号分配的员工数量 X 和字母长度 Y 的情况下，求出数字部分的最短长度 Z。

解题思路

字母部分的组合数量: 由于字母只能是小写英文字母（a-z），总共有26个字母，因此字母部分的总数可以表示为 $26^Y$ 。

数字部分的组合数量: 数字部分可以由任意位数的数字组成，且数字部分可以有前导0，因此对于Z位数字，总共有 $10^Z$ 种组合。

目标: 总的工号数应该满足能分配给至少 X 个员工，所以要找出一个最小的 Z，使得字母部分和数字部分的组合数量 $26^Y \times 10^Z$ 不小于 X。

二分查找: 我们可以用二分法来快速找到数字部分的最小长度 Z。初始的搜索区间为 [0, 20]，然后逐步缩小区间，通过判断 $26^Y \times 10^Z$ 是否大于等于 X 来更新搜索区间。

时间复杂度

二分查找的时间复杂度为 O(log⁡Z)，由于最大搜索区间为20，因此时间复杂度接近常数时间。

Java

import java.util.Scanner;
/**
 * @author code5bug
 */
public class Main {
    
    public static boolean ok(long x, int y, int z) {
        // 判断26^y * 10^z 是否大于等于 X
        return Math.pow(26, y) * Math.pow(10, z) >= x;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long x = scanner.nextLong();
        int y = scanner.nextInt();
        
        int left = 0, right = 20;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (ok(x, y, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        
        System.out.println(right);
    }
}

Python

import math

def ok(x, y, z):
    # 判断26^y * 10^z 是否大于等于 X
    return math.pow(26, y) * math.pow(10, z) >= x

def main():
    x, y = map(int, input().split())
    
    left, right = 0, 20
    while left + 1 < right:
        mid = (left + right) // 2
        if ok(x, y, mid):
            right = mid
        else:
            left = mid
    
    print(right)

if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

bool ok(long long x, int y, int z)
{
    // 判断26^y * 10^z 是否大于等于 X
    return pow(26, y) * pow(10, z) >= x;
}

int main()
{
    long long x;
    int       y;
    cin >> x >> y;

    int left = 0, right = 20;
    while (left + 1 < right) {
        int mid = (left + right) / 2;
        if (ok(x, y, mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }

    cout << right << endl;
}