Radish and his baby Radish want to play ball, but not the surface games that humans…
- User
Radish and his baby Radish want to play ball, but not the surface games that humans play! In front of them at the beginning of each game, there are a number of boxes and in each box there are a number (larger than 1) of balls. Anyone on their turn can perform exactly one of the following actions on a deck that has at least 2 balls, and anyone who fails to perform an action loses the game. Note that radish is always the starter of the game because it is smaller.
A bunch of a a the ball into two groups with 1 1 and a
1 a−1 is a dividing ball. A bunch of a a the ball into two groups with ⌊ a 2 ⌋ ⌊ 2 a ⌋ and ⌈ a 2 ⌉ ⌈ 2 a ⌉ Split ball. A bunch of a a the ball into two groups with ⌊ a ⌋ ⌊ a ⌋ and a
⌊ a ⌋ a−⌊ a ⌋ divide the ball. To know the definition of terms ⌊ a ⌋ ⌊a⌋ and ⌈ a ⌉ ⌈a⌉ You can read the floor and ceiling link.
input In the first line of the input, the integer t t which represents the number of games played between Radish and Radish. 1 ≤ t ≤ 100 1≤t≤100
Then comes the information of each game. In the first line of information for each game, k k or the same number of categories comes and then in the next line, k k is an integer that i The i-th of them c i c i It is named and indicates the number of balls in the bunch i is i 1 ≤ k ≤ 10 , 000 1≤k≤10,000 2 ≤ c i ≤ 100 , 000 2≤c i ≤100,000
output For each game, output Torob if Radish won with optimal game and Torob Che if Radish won with optimal game.
Example Sample entry 1 4 1 6 2 3 3 1 9 3 2 2 2 Plain text Sample output 1 Torob Che Torob Torob Torob Che
- Assistant
To solve this problem, we need to determine whether the starting player (Radish) can force a win in each game based on the given configurations of balls in boxes. Here's a step-by-step breakdown of the solution:
Game Rules Recap:
- Each game consists of several boxes, each containing a certain number of balls.
- Players take turns splitting a box of balls according to specific rules.
- The player who cannot make a move loses the game.
Strategy:
-
Grundy Numbers (Nimber Theory):
- Each game's configuration can be analyzed using Grundy numbers.
- For each box with
c_iballs:- If
c_iis even, the Grundy number is1. - If
c_iis odd, the Grundy number is0.
- If
- The overall game state is determined by the XOR (exclusive OR) of all Grundy numbers from each box.
- If the XOR result is non-zero, the starting player (Radish) can force a win. Otherwise, the second player can win.
-
Implementation Steps:
- For each game, count the number of boxes with an even number of balls.
- If the count of even-numbered boxes is odd, Radish can force a win.
- Otherwise, Radish cannot force a win.
-
Output:
- If Radish can force a win, output
"Torob Che". - If Radish cannot force a win, output
"Torob".
- If Radish can force a win, output
Example Walkthrough:
-
Test Case 1:
- Boxes:
[6](1 box, even) - Count of even boxes: 1 (odd)
- Output:
"Torob Che"
- Boxes:
-
Test Case 2:
- Boxes:
[3, 3](2 boxes, both odd) - Count of even boxes: 0 (even)
- Output:
"Torob"
- Boxes:
-
Test Case 3:
- Boxes:
[9](1 box, odd) - Count of even boxes: 0 (even)
- Output:
"Torob"
- Boxes:
-
Test Case 4:
- Boxes:
[2, 2, 2](3 boxes, all even) - Count of even boxes: 3 (odd)
- Output:
"Torob Che"
- Boxes:
Final Solution:
Based on the above reasoning, the implementation can be simplified to counting the number of boxes with an even number of balls and determining the winner accordingly.
def main(): import sys input = sys.stdin.read data = input().split() idx = 0 t = int(data[idx]) idx +=1 for _ in range(t): k = int(data[idx]) idx +=1 count_even =0 for _ in range(k): c_i = int(data[idx]) if c_i %2 ==0: count_even +=1 idx +=1 if count_even %2 ==1: print("Torob Che") else: print("Torob") if __name__ == "__main__": main()