CF408B.Garland
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Once little Vasya read an article in a magazine on how to make beautiful handmade garland from colored paper. Vasya immediately went to the store and bought n colored sheets of paper, the area of each sheet is 1 square meter.
The garland must consist of exactly m pieces of colored paper of arbitrary area, each piece should be of a certain color. To make the garland, Vasya can arbitrarily cut his existing colored sheets into pieces. Vasya is not obliged to use all the sheets to make the garland.
Vasya wants the garland to be as attractive as possible, so he wants to maximize the total area of m pieces of paper in the garland. Calculate what the maximum total area of the pieces of paper in the garland Vasya can get.
从前,小瓦夏在一本杂志上读到一篇关于如何用彩纸制作精美手工花环的文章。瓦夏立刻前往商店,买了 n 张彩纸,每张纸的面积均为 1 平方米。
该花环必须恰好由 m 片彩纸组成,每片纸的面积可以是任意正数,但必须具有某种确定的颜色。为了制作花环,瓦夏可以随意将他已有的彩纸裁剪成若干片。瓦夏并不需要使用全部彩纸来制作花环。
瓦夏希望花环尽可能美观,因此他希望最大化花环中这 m 片纸的总面积。请计算瓦夏所能获得的花环中纸片总面积的最大值。
输入格式
The first line contains a non-empty sequence of n (1 ≤ n ≤ 1000) small English letters ("a"..."z"). Each letter means that Vasya has a sheet of paper of the corresponding color.
The second line contains a non-empty sequence of m (1 ≤ m ≤ 1000) small English letters that correspond to the colors of the pieces of paper in the garland that Vasya wants to make.
第一行包含一个非空的、由 n(1 ≤ n ≤ 1000)个小写英文字母("a"..."z")组成的序列。每个字母表示瓦夏拥有一张对应颜色的纸。
第二行包含一个非空的、由 m(1 ≤ m ≤ 1000)个小写英文字母组成的序列,这些字母对应瓦夏想要制作的彩链中各纸片的颜色。
输出格式
Print an integer that is the maximum possible total area of the pieces of paper in the garland Vasya wants to get or -1, if it is impossible to make the garland from the sheets he's got. It is guaranteed that the answer is always an integer.
输出一个整数,表示瓦夏想要制作的花环中纸片的最大可能总面积;如果无法用他现有的纸张制作该花环,则输出 -1。保证答案始终为整数。
输入输出样例
输入#1
aaabbac aabbccac
输出#1
6
输入#2
a z
输出#2
-1
说明/提示
In the first test sample Vasya can make an garland of area 6: he can use both sheets of color b, three (but not four) sheets of color a and cut a single sheet of color c in three, for example, equal pieces. Vasya can use the resulting pieces to make a garland of area 6.
In the second test sample Vasya cannot make a garland at all — he doesn't have a sheet of color z.
在第一个测试样例中,瓦西娅可以制作一个面积为 6 的花环:他可以使用两张颜色为 b 的纸、三张(但不能是四张)颜色为 a 的纸,并将一张颜色为 c 的纸裁剪成三块(例如,裁剪成三块相等的部分)。瓦西娅可以利用这些得到的纸片制作一个面积为 6 的花环。
在第二个测试样例中,瓦西娅根本无法制作花环——他没有颜色为 z 的纸。
输入解题思路,AI测评打分。不知道怎么写?