问题3286--抢分游戏3286: 抢分游戏
时间限制: 2 Sec 内存限制: 512 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
雨荨和云海正在玩一个和字符串有关的游戏。
游戏规则如下:有一个字典,里面有N个单词(可重复)。雨荨先任意挑选一个小写字母,要保证这个字符在N个单词里出现过。然后云海选择任意一个小写字母,添加在雨荨选的字符的头或者尾,形成一个新的字符串,并且要保证这个新形成的字符串,是字典里某个单词的子串(注意不是子序列,子串必须连续)。然后雨荨按照相同的做法,选取任意一个小写字母,添加在当前字符串的头或者尾。谁不能继续操作,谁就输了,对方就赢了。
雨荨和云海还设计了一个积分规则:
如果形成了一个字符串S,那么当前选手获得score(S)的分数,也就是说第一轮雨荨选的字符,由雨荨得分,然后是云海,接着又是雨荨……
score(S)=(∑value(S[i]))*max{value(S[i])}+num(s) 1<=i<=|S|
1) 其中|S|表示S的长度
2) value(c)代表一个字符的分值,小写字母a分值为1,b为2….z为26。
3) num(s)表示字符串s在字典里是num(s)个单词的子串。
现在请你输出,雨荨和云海谁或获胜,以及最后他俩的分数。他们两都会以最优策略
来玩这个游戏,并且他们会先考虑获胜,然后最大化自己的分数,最后再想方设法最小化另一方的分数。
输入
输入文件名为score.in。
第一行一个整数N,代表字典里单词个数。
接下来N行,每行一个字符串代表字典里的一个单词。
输出
输出文件名为score.out。
输出的第一行为一个字符串,如果雨荨获胜,输出ChuYuxun,否则输出MuRongyunhai。
第二行为一个空格隔开两个整数,依次代表雨荨和云海的得分。
样例输入
【样例1】
2
aba
abac
【样例2】
3
artem
nik
max
样例输出
【样例1】
MuRongyunhai
29 35
【样例2】
ChuYuxun
2403 1882
来源/分类
[提交] [状态]