Sequence Folding Game
InterviewTime limit1sMemory limit128 MB
Repeatedly fold the list by adding symmetric pairs until two numbers remain, then Alice wins when the first is larger.
- Level
Easy2 of 10
- Topics
- Simulation, Array
- Solved
- No attempts yet
Problem
Alice and Bob play a sequence folding game. The game runs in this order.
- Pick an integer that is at least 2.
- Build a sequence of integers.
- If is 2, jump to step 6.
- Fold the sequence into a new one by adding the first number to the th, the second to the th, and so on. When is odd, the middle number is added to itself.
- Replace with and go back to step 3.
- Two numbers are left. Alice wins when the first number is greater than the second, and Bob wins in every other case.
Given a sequence of integers, write a program that finds the winner of the game.
Input
The first line has the number of test cases (). Each test case starts with a line holding the length of the sequence (), followed by a line with the integers of the sequence separated by spaces. Every integer fits in the signed 32-bit range.
Output
For each test case print one line, either Case #x: Alice or Case #x: Bob, where is the test case number starting from 1. Print Alice when Alice wins and Bob when Bob wins.