수열 접기 게임
면접 대비시간 제한1초메모리 제한128 MB
대칭 쌍을 더하는 접기를 두 수가 남을 때까지 반복하고 첫 수가 더 크면 Alice가 승리한다고 판정합니다.
문제
앨리스와 밥이 수열 접기 게임을 한다. 게임은 다음 순서로 진행된다.
- 2보다 크거나 같은 정수 을 하나 고른다.
- 정수 개로 이루어진 수열을 만든다.
- 이 2이면 6번으로 넘어간다.
- 첫 번째 수와 번째 수를 더하고, 두 번째 수와 번째 수를 더하는 식으로 수열을 접어 새 수열을 만든다. 이 홀수이면 가운데 수는 자기 자신과 더한다.
- 을 로 바꾸고 3번으로 돌아간다.
- 수열에 수가 두 개 남는다. 첫 번째 수가 두 번째 수보다 크면 앨리스가 이기고, 그 외에는 밥이 이긴다.
정수 개로 이루어진 수열이 주어지면 게임의 승자를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 ()가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 길이 ()이 주어지고, 둘째 줄에는 수열을 이루는 정수 개가 공백으로 구분되어 주어진다. 각 정수는 32비트 부호 있는 정수 범위에 들어간다.
출력
각 테스트 케이스마다 한 줄에 Case #x: Alice 또는 Case #x: Bob을 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 앨리스가 이기면 Alice, 밥이 이기면 Bob을 출력한다.