shunfurh
编程介的小学生
2017-09-26 09:22

Judicious Strategy

  • play
  • dictionary
  • lines
  • word
  • substring

Problem Description
Alice and Bob is now playing a game about strings.
There is a dictionary containing n words (words might be same). Alice choose a lowercase English letter arbitrarily first, but this letter should appear in at least one of these n words. Then Bob choose a lowercase English letter arbitrarily to add it before or after the letter Alice chose. So Bob gets a new string now. This new string should also be a substring (consecutive subsequence) of at least one strings in the dictionary. After that, it's Alice's turn. Alice should do the same thing, choosing a letter and add it before or after the current string, making a new string. At every moment, the string they made should always be a substring of at least one strings in the dictionary. The player who can't operate first lose the game and the other one win.
Besides, each player has a score. The score is calculated by the following rule:
If the string S is now made, the current player will get score(S) points. It means that Alice will score in the first round, then Bob, then Alice...
score(S)=⎡⎣⎛⎝∑i=1|S|value(Si)⎞⎠×maxi=1|S|value(Si)⎤⎦+occ(S)

where

  1. |S| means the length of S.
  2. value(c) represents the value of letter c. The score of letter a'' is 1,b'' is 2, ..., ``z'' is 26.
  3. occ(S) means the time that S occurs as a substring in the dictionary, each word is counted just once.

Alice and Bob will play with best strategy. That is to say, they will consider to win first and then maximize their score, after that they will consider to minimize the score of others.
Please determine who will win the game, and report the final scores they will earn during the whole game.

Input
The input contains several test cases, no more than 10 test cases.
In each test case, the first line contains an integer n(1≤n≤30), denoting the number of words in the dictionary.
In the next n lines, each line contains a non-empty string wordi, denoting a word in the dictionary. The string is composed of lowercase English letters and its length will not exceed 30.

Output
For each test case, output a string in the first line. If Alice will win ,output ''Alice'', otherwise output ''Bob''.
Then print two integers A and B in second line, denoting the final score of Alice and Bob.

Sample Input
2
aba
abac
3
artem
nik
max

Sample Output
Bob
29 35
Alice
2403 1882

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

2条回答

为你推荐