Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5635 --4、口袋 (pocket)
5635: 4、口袋 (pocket)
警告!
题目
状态
题解
题目描述
克拉拉同学平时就喜欢一些奇奇怪怪的东西,她有一个神奇的口袋,她能从口袋里拿出各种神奇的东西。 某一天她发现口袋里出现了一些像数字形状的物品, 我们用 0 到 9 这十种数字来表示不同的物品。 克拉拉有一个非常喜欢的数字 x, 现在她想用口袋里的给出的这些数字形状的物品来组成尽可能多的 x,每个物品只能用一次。 组装过程中克拉拉发现这些像数字形状的物品中,“2” 和 “5”倒过来特别像,“6” 和 “9” 倒过来也特别像,所以她可以用 2 和 5 互相代替,也能用 6 和 9互相代替(其他的不能代替)。 举个例子,克拉拉喜欢数字 42,现在口袋里能拿出来顺序为 “23454” 这五种物品,因此她可以用第一个物品 “2” 和第三个物品 “4” 组成 42(可以组成 24,但不是需要的),还能用第四个物品 “5” 和第五个物品 “4" 组成 42(其中 5 倒过来可以当作 2 )。 现在想要知道这些物品最多能组成几个克拉拉最喜欢的数字。 请你编程帮克拉拉解决这个问题,并输出能用物品组成 x 的最多的个数。
输入
第一行为一个正整数 x,表示克拉拉最喜欢的数字。 第二行为一个字符串,字符串每一位为 ‘0’ 到 ‘9’ 的某个字符,字 符串长度为物品的个数(数字之间没有其他符号)。
输出
一行,一个整数,表示能用物品拼成最多的 x 的个数(拼成x的次数)。
样例输入输出
输入#1
复制
42 23454
输出#1
复制
2
输入#2
复制
169 21891919
输出#2
复制
1
输入#3
复制
801 12345678111
输出#3
复制
0
提示
样例 1 说明 (2, 4)和 (5, 4)拼成 42,其中 5 可以倒过来当作 2。可以证明不能再多拼成一个 42 了。 样例 2 说明 2-“1”-8-“9”-1-“9”-1-9,可以用(1,9,9)拼成 169,第一个 9 可以倒过来当 6 使用。因为每个数字只能用一次,因此最多只能拼成一个 169。 【数据范围和限制】 对于 30% 的数据,1 ≤ x ≤ 100,字符串长度不超过 20。 其中 10% 的数据保证 x < 10, 另外 10% 的数据保证 x 中不出现 2、5、6、9。 对于 60% 的数据,1 ≤ x ≤ 1000, 字符串长度不超过 100; 对于 100% 的数据,1 ≤ x ≤ 100000,字符串长度不超过 200000
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及-
标签
字符串
点击显示
if ($pr_flag) { ?>
递交数
34
已通过
12
} ;?>
通过率
36%
时间限制
1 秒
内存限制
128 MB
来源
2021CSP山东小学
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和