#P1032. 姓名团
姓名团
题目描述
在某一个平行世界中,每个人的姓名有三个字,且三个字的读音都必须不相同,否则姓名不合法。例如 ji-wei-jiu 是一个合法的名字;而 yao-wang 则不是,因为只有两个字;li-yi-yi 也不是,因为有两个读音相同的字。
如果有三个人的名字具有题目中的特性,则我们称这三个人为一个“姓名团”。特性如下:你可以选出三个不同的字,使得每个字都被这三个人中的至少两人的名字包含。
例如第一个人叫 wu-si-cheng,第二个人叫 wu-jia-han,第三个人叫 chen-si-han。那么当你选择 wu 的时候,前两个人包含这个字,选择 si 的时候,第一和第三个人包含这个字,选择 han 的时候,第二和第三个人包含这个字。(只需要包含这个字即可,无需关心这个字在名字中的位置)
即对于 wu-si-han 这三个字,每一个字都被至少两人包含。
注意: 每个人只能处于一个姓名团中,在任意范围内,不同人之间的名字可以相同。
现在你有一个包含 个字的字库,每个字可以用 次,我们假设所有字的使用次数之和为 (保证 sum 是 3 的倍数),那么你就可以造出 个人名出来。请问你最多能造出多少个姓名团。
如果不能造出 个合法人名,输出 -1。
输入格式
第一行输入一个整数 ,表示字库中共有 个字。接下来一行包含 个正整数 ,分别表示每个字能够使用的次数,保证所有 之和是 3 的倍数。
输出格式
输出一行一个整数表示结果。
3
10 1 1
-1
3
4 4 4
1
样例 2 说明:总共可以造出 4 个名字一样的人,但是由于一个姓名团需要包含 3 个人,所以只能有一个姓名团。
测试点信息
测试点 | 数据范围 | 特殊性质 |
---|---|---|
1-3 | ||
4-6 | 答案要么为-1要么为100,且所有 之和为 900,保证其它数据没有此性质,即你可以通过判断所有 之和是否为 900 来识别本组数据 | |
7-10 |