CF38F.Smart Boy

提高+/省选-

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Once Petya and Vasya invented a new game and called it "Smart Boy". They located a certain set of words — the dictionary — for the game. It is admissible for the dictionary to contain similar words.

The rules of the game are as follows: first the first player chooses any letter (a word as long as 1) from any word from the dictionary and writes it down on a piece of paper. The second player adds some other letter to this one's initial or final position, thus making a word as long as 2, then it's the first player's turn again, he adds a letter in the beginning or in the end thus making a word as long as 3 and so on. But the player mustn't break one condition: the newly created word must be a substring of a word from a dictionary. The player who can't add a letter to the current word without breaking the condition loses.

Also if by the end of a turn a certain string s is written on paper, then the player, whose turn it just has been, gets a number of points according to the formula:

where

  • is a sequence number of symbol c in Latin alphabet, numbered starting from 1. For example, , and .
  • is the number of words from the dictionary where the line s occurs as a substring at least once.

Your task is to learn who will win the game and what the final score will be. Every player plays optimally and most of all tries to win, then — to maximize the number of his points, then — to minimize the number of the points of the opponent.

曾经,佩佳和瓦夏发明了一款新游戏,并将其命名为“聪明男孩”。他们为该游戏准备了一个特定的单词集合——词典。词典中允许出现相同的单词。

游戏规则如下:首先,第一位玩家从词典中的任意一个单词中选择任意一个字母(即长度为 1 的字符串),并将其写在纸上;接着,第二位玩家在该字母的开头或末尾添加另一个字母,从而构成一个长度为 2 的字符串;然后轮到第一位玩家,他同样在当前字符串的开头或末尾添加一个字母,使其长度变为 3;依此类推。但玩家必须遵守一个条件:每次新构成的字符串必须是词典中某个单词的子串。若某位玩家无法在不违反该条件的前提下向当前字符串添加一个字母,则该玩家输掉游戏。

此外,若在某一轮操作结束时,纸上所写的字符串为 $ s $,则刚刚完成本轮操作的玩家将根据以下公式获得相应分数:

其中:

  • $ \text{pos}(c) $ 表示字符 $ c $ 在拉丁字母表中的序号(从 1 开始编号)。例如,$ \text{pos}(\text{a}) = 1 $,而 $ \text{pos}(\text{z}) = 26 $。
  • $ \text{cnt}(s) $ 表示词典中至少包含一次子串 $ s $ 的单词个数。

你的任务是判断谁将赢得游戏,以及最终的得分是多少。双方均采取最优策略:首要目标是获胜,其次是在确保获胜的前提下最大化自身得分,最后是在前两者均相同的情况下最小化对手的得分。

输入格式

The first input line contains an integer n which is the number of words in the located dictionary (1 ≤ n ≤ 30). The n lines contain the words from the dictionary — one word is written on one line. Those lines are nonempty, consisting of Latin lower-case characters no longer than 30 characters. Equal words can be in the list of words.

第一行输入包含一个整数 nn,表示字典中单词的数量(1≤n≤301 \leq n \leq 30)。接下来的 nn 行包含字典中的单词——每行一个单词。这些行非空,仅由小写拉丁字母组成,且每个单词长度不超过 30 个字符。单词列表中可能出现重复的单词。

输出格式

On the first output line print a line "First" or "Second" which means who will win the game. On the second line output the number of points of the first player and the number of points of the second player after the game ends. Separate the numbers by a single space.

在第一行输出一行“First”或“Second”,表示谁将赢得游戏。
在第二行输出游戏结束后第一位玩家的得分和第二位玩家的得分,两个数字之间用一个空格分隔。

输入输出样例

  • 输入#1

    2
    aba
    abac

    输出#1

    Second
    29 35
  • 输入#2

    3
    artem
    nik
    max

    输出#2

    First
    2403 1882

输入解题思路,AI测评打分。不知道怎么写?

首页