# [Solution] Subtle Substring Subtraction solution codeforces

Subtle Substring Subtraction solution codeforces – Alice and Bob are playing a game with strings. There will be π‘tΒ rounds in the game. In each round, there will be a stringΒ π sΒ consisting of lowercase English letters.

## [Solution] Subtle Substring Subtraction solution codeforces

Alice moves first and both the players take alternate turns.Β Alice is allowed to remove any substring of even length (possibly empty) and Bob is allowed to remove any substring of odd length fromΒ π s.

More formally, if there was a stringΒ π =π 1π 2β¦π πs=s1s2β¦skΒ the player can choose a substringΒ π ππ π+1β¦π πβ1π πslsl+1β¦srβ1srΒ with length of corresponding parity and remove it. After that the string will becomeΒ π =π 1β¦π πβ1π π+1β¦π πs=s1β¦slβ1sr+1β¦sk.

After the string becomes empty, the round ends and each player calculates his/her score for this round. The score of a player is the sum of values of all characters removed by him/her. The value ofΒ πaΒ isΒ 11, the value ofΒ πbΒ isΒ 22, the value ofΒ πcΒ isΒ 33,Β β¦β¦, and the value ofΒ π£zΒ isΒ 2626. The player with higher score wins the round. For each round, determine the winner and the difference between winner’s and loser’s scores. Assume that both players play optimally to maximize their score. It can be proved that a draw is impossible.

Input

The first line of input contains a single integerΒ π‘tΒ (1β€π‘β€5β1041β€tβ€5β104) denoting the number of rounds.

Each of the nextΒ π‘tΒ lines contain a single stringΒ π sΒ (1β€|π |β€2β1051β€|s|β€2β105) consisting of lowercase English letters, denoting the string used for the round. HereΒ |π ||s|Β denotes the length of the stringΒ π s.

It is guaranteed that the sum ofΒ |π ||s|Β over all rounds does not exceedΒ 2β1052β105.

## [Solution] Subtle Substring Subtraction solution codeforces

For each round, print a single line containing a string and an integer. If Alice wins the round, the string must be “Alice“. If Bob wins the round, the string must be “Bob“. The integer must be the difference between their scores assuming both players play optimally.

Example
input

Copy
5
aba
abc
cba
n
codeforces

output

Copy
Alice 2
Alice 4
Alice 4
Bob 14
Alice 93


## Subtle Substring Subtraction solution codeforces

For the first round,Β “πππ”βββββπ°πππππππ”β“π”βββπ±πππβ“”“aba”βAlice”aba”β”a”βBob”a”β””. Alice’s total score isΒ 1+2=31+2=3. Bob’s total score isΒ 11.

For the second round,Β “πππ”βββββπ°ππππ“πππβ“π”βββπ±πππβ“”“abc”βAlice”abc”β”a”βBob”a”β””. Alice’s total score isΒ 2+3=52+3=5. Bob’s total score isΒ 11.

For the third round,Β “πππ”βββββπ°πππππππ”β“π”βββπ±πππβ“”“cba”βAlice”cba”β”a”βBob”a”β””. Alice’s total score isΒ 3+2=53+2=5. Bob’s total score isΒ 11.

For the fourth round,Β “π”βββββπ°ππππ“π”β“π”βββπ±πππβ“”“n”βAlice”n”β”n”βBob”n”β””. Alice’s total score isΒ 00. Bob’s total score isΒ 1414.

For the fifth round,Β “ππππππππππ”βββββπ°ππππππππππππππβ“”“codeforces”βAlice”codeforces”β””. Alice’s total score isΒ 3+15+4+5+6+15+18+3+5+19=933+15+4+5+6+15+18+3+5+19=93. Bob’s total score isΒ 00.