# [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𝑡51041≤t≤5⋅104) denoting the number of rounds.

Each of the next 𝑡t lines contain a single string 𝑠s (1|𝑠|21051≤|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 21052⋅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.