Subtle Substring Subtraction Solution | Codeforces Problem Solution 2022

Subtle Substring Subtraction Solution | Codeforces Problem Solution 2022 

A. Subtle Substring Subtraction

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

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=s_1{s}_2\dots s_k$ the player can choose a substring 𝑠𝑙𝑠𝑙+1…𝑠𝑟−1𝑠𝑟$s_l{s}_{l+1}\dots s_{r-1}{s}_r$ with length of corresponding parity and remove it. After that the string will become 𝑠=𝑠1…𝑠𝑙−1𝑠𝑟+1…𝑠𝑘$s=s_1\dots s_{l-1}{s}_{r+1}\dots s_k$.

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 𝚊$\mathtt{\text{a}}$ is 1$1$, the value of 𝚋$\mathtt{\text{b}}$ is 2$2$, the value of 𝚌$\mathtt{\text{c}}$ is 3$3$, …$\dots$, and the value of 𝚣$\mathtt{\text{z}}$ is 26$26$. 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.

Solution Click Below:-  CLICK HERE

Input

The first line of input contains a single integer 𝑡$t$ (1≤𝑡≤5⋅104$1\le t\le 5\cdot {10}^4$) denoting the number of rounds.

Lost Arithmetic Progression Solution | Codeforces Problem Solution 2022

Power or XOR? Solution | Codeforces Problem Solution 2022 

Anti-Theft Road Planning Solution | Codeforces Problem Solution 2022 

A Perfectly Balanced String? Solution | Codeforces Problem Solution 2022 

Palindrome Basis Solution | Codeforces Problem Solution 2022 

Subtle Substring Subtraction Solution | Codeforces Problem Solution 2022 

Each of the next 𝑡$t$ lines contain a single string 𝑠$s$ (1≤|𝑠|≤2⋅105$1\le |s|\le 2\cdot {10}^5$) 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⋅105$2\cdot {10}^5$.

Output

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.

Join Now for Solution:-