首页 > 试题广场 >

烘焙店的配方检查

[编程题]烘焙店的配方检查
  • 热度指数:113 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 512M,其他语言1024M
  • 算法知识视频讲解
一家颇受欢迎的烘焙店以其独特的招牌蛋糕而闻名。
这款蛋糕的配方非常讲究,制作过程严格按照一个固定的主配方 T 进行,其中包含了按顺序添加的各种原料。

为了提高效率,店里准备了多种预先打包好的半成品配料包。
现在,烘焙师需要从一批配料包中,快速找出所有与主配方 T 兼容的配料包。

一个配料包 C_i 被认为是“兼容的”,必须满足以下条件:
1. 配料包 C_i 中的原料种类和顺序,必须与主配方 T 的起始部分完全一致。也就是说,C_i 必须是 T 的一个前缀。
2. 配料包 C_i 的长度不能超过主配方 T 的长度。

烘焙师希望将所有兼容的配料包找出来,并按照“完整度”从高到低进行排序展示。
一个配料包的“完整度”由其包含的原料数量决定——包含的原料越多,说明它越接近最终成品,完整度越高。

您的任务是编写一个程序,帮助烘焙师完成这项工作。
程序需要统计每种兼容配料包出现的次数,并按照完整度从高到低(即字符串长度从长到短)的顺序输出。

输入描述:
输入为一行字符串,由空格分隔。

第一个字符串是主配方 T
后续的字符串是待检查的配料包 C_1, C_2, \dots, C_k
配料包的最大数量为 100 个。
输入中可能包含重复的配料包字符串。


输出描述:
输出所有兼容的配料包及其出现的次数,每个占一行,格式为 `配料包字符串 出现次数`。

输出结果需按照完整度从高到低(即字符串长度从长到短)的顺序排列。
如果没有任何一个配料包是兼容的,则单独输出一行 null。
示例1

输入

flour-egg-sugar-butter flour flour-egg-sugar flour-egg flour

输出

flour-egg-sugar 1
flour-egg 1
flour 2
示例2

输入

flour-egg-sugar-butter flour-butter flour-salt

输出

null

备注:
本题由牛友@Charles 整理上传
def isCompatible(t : str, c : str):
    if len(c) > len(t):
        return 0
    return t[:len(c)] == c

s = input().split()
t = s.pop(0)
s.sort(key=len, reverse=True)
compatible_pkg = {}
for pkg in s:
    if isCompatible(t, pkg):
        if pkg in compatible_pkg:
            compatible_pkg[pkg] += 1
        else:
            compatible_pkg[pkg] = 1
if compatible_pkg:
    for c_pkg, num in compatible_pkg.items():
        print(c_pkg, num)
else:
    print('null')

发表于 今天 17:56:46 回复(0)