시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 275 168 156 61.660%

문제

상근이와 창영이는 수열 접기 게임을 해보려고 한다. 게임은 아래와 같이 진행된다.

  1. 2보다 크거나 같은 정수 하나를 임의로 고른다.
  2. 임의의 정수 N개로 이루어진 수열을 만든다.
  3. N이 2인 경우에는 단계 6으로 이동한다.
  4. 첫 번째 수를 N번째 수와 더하고, 두 번째 수를 N-1번째 수와 더하는 형식으로 수열을 접어 새로운 수열을 하나 만든다. N이 홀수인 경우에는 가운데 수를 자기 자신과 더한다. 아래 그림 1은 접는 과정을 나타낸다.
  5. N을 ceil(N/2)로 바꾸고, 단계 3으로 이동한다.
  6. 이제 수열에는 숫자 두 개가 포함되어 있다. 첫 번째 수가 두 번째 수보다 큰 경우에는 상근이가 이기고, 나머지 경우는 창영이가 이긴다.

그림 1.a 접기 전

그림 1.b 한 번 접고 난 후

그림 1.c 한 번 더 접고 난 후, 상근이가 이겼다!

정수 N개로 이루어진 수열이 주어졌을 때, 수열 접기 게임의 승자를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열에 포함된 수의 개수 N (2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열이 주어진다. 수열을 이루는 숫자는 32비트 부호있는 정수범위이다.

출력

각 테스트 케이스마다 상근이가 이긴 경우에는 Alice, 창영이가 이긴 경우에는 Bob을 테스트 케이스 번호와 함께 출력한다.

예제 입력 1

2
5
2 5 10 3 -4
3
5 4 -3

예제 출력 1

Case #1: Alice
Case #2: Bob

힌트

W3sicHJvYmxlbV9pZCI6IjkzNTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM1ZjQgXHVjODExXHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWMyMThcdWM1ZjQgXHVjODExXHVhZTMwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NzRcdWJjZjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFjOGNcdWM3ODRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWM5YzRcdWQ1ODlcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Mlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjNzg0XHVjNzU4XHViODVjIFx1YWNlMFx1Yjk3OFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzg0XHVjNzU4XHVjNzU4IFx1YzgxNVx1YzIxOCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGUwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5OXHVjNzc0IDJcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjJlOFx1YWNjNCA2XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWI5N2MgTlx1YmM4OFx1YzlmOCBcdWMyMThcdWM2NDAgXHViMzU0XHVkNTU4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIxOFx1Yjk3YyBOLTFcdWJjODhcdWM5ZjggXHVjMjE4XHVjNjQwIFx1YjM1NFx1ZDU1OFx1YjI5NCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YzgxMVx1YzViNCBcdWMwYzhcdWI4NWNcdWM2YjQgXHVjMjE4XHVjNWY0XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTBcdWIyZTQuIE5cdWM3NzQgXHVkNjQwXHVjMjE4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjMjE4XHViOTdjIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWFjZmMgXHViMzU0XHVkNTVjXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjIDFcdWM3NDAgXHVjODExXHViMjk0IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvbGk+XHJcblx0PGxpPk5cdWM3NDQgY2VpbChOXC8yKVx1Yjg1YyBcdWJjMTRcdWFmYjhcdWFjZTAsIFx1YjJlOFx1YWNjNCAzXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNzc0XHVjODFjIFx1YzIxOFx1YzVmNFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTAgXHViNDUwIFx1YWMxY1x1YWMwMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzIxOFx1YWMwMCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIxOFx1YmNmNFx1YjJlNCBcdWQwNzAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzBcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzNFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mb2xkMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDFweDsgd2lkdGg6NDk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAxLmEgXHVjODExXHVhZTMwIFx1YzgwNDxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mb2xkMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzNweDsgd2lkdGg6MzI3cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAxLmIgXHVkNTVjIFx1YmM4OCBcdWM4MTFcdWFjZTAgXHViMDljIFx1ZDZjNDxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9mb2xkMy5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjRweDsgd2lkdGg6Mzc2cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyAxLmMgXHVkNTVjIFx1YmM4OCBcdWIzNTQgXHVjODExXHVhY2UwIFx1YjA5YyBcdWQ2YzQsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3NzRcdWFjYmNcdWIyZTQhPFwvcD5cclxuXHJcbjxwPlx1YzgxNVx1YzIxOCBOXHVhYzFjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMjE4XHVjNWY0IFx1YzgxMVx1YWUzMCBcdWFjOGNcdWM3ODRcdWM3NTggXHVjMmI5XHVjNzkwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUICgxICZsZTsgVCAmbGU7IDEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MWMgXHVjMjE4XHVjNzU4IFx1YWMxY1x1YzIxOCBOICgyICZsZTsgTiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjMjJiXHVjNzkwXHViMjk0IDMyXHViZTQ0XHVkMmI4IFx1YmQ4MFx1ZDYzOFx1Yzc4OFx1YjI5NCBcdWM4MTVcdWMyMThcdWJjOTRcdWM3MDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzNCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgQWxpY2UsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWM3NzRcdWFlMzQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IEJvYlx1Yzc0NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1YzY0MCBcdWQ1NjhcdWFlZDggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzNTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTZXF1ZW5jZSBGb2xkaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5BbGljZSBhbmQgQm9iIGFyZSBwcmFjdGljaW5nIGhhcmQgZm9yIHRoZSBuZXcgSUNQQyBzZWFzb24uIFRoZXkgaG9sZCBtYW55IHByaXZhdGUgY29udGVzdHMgd2hlcmUgb25seSB0aGUgdHdvIG9mIHRoZW0gY29tcGV0ZSBhZ2FpbnN0IGVhY2ggb3RoZXIuIFRoZXkgYWxtb3N0IGhhdmUgaWRlbnRpY2FsIGtub3dsZWRnZSBhbmQgc2tpbGxzLCB0aGUgbWF0dGVyIHdoaWNoIHJlc3VsdHMgbWFueSB0aW1lcyBpbiB0aWVzIGluIGJvdGggdGhlIG51bWJlciBvZiBwcm9ibGVtcyBzb2x2ZWQgYW5kIGluIHRpbWUgcGVuYWx0eSEgVG8gYnJlYWsgdGhlIHRpZSwgQWxpY2UgYW5kIEJvYiBpbnZlbnRlZCBhIHRpZSBicmVha2VyIHRlY2huaXF1ZSBjYWxsZWQgc2VxdWVuY2UgZm9sZGluZyEgVGhlIGZvbGxvd2luZyBhcmUgdGhlIHN0ZXBzIG9mIHRoaXMgdGVjaG5pcXVlOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkdlbmVyYXRlIGEgcmFuZG9tIGludGVnZXIgTiAmZ3Q7PSAyLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5HZW5lcmF0ZSBhIHNlcXVlbmNlIG9mIE4gcmFuZG9tIGludGVnZXJzLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiBOID0gMiBnbyB0byBzdGVwIDYuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkZvbGQgdGhlIHNlcXVlbmNlIGJ5IGFkZGluZyB0aGUgTnRoIGVsZW1lbnQgdG8gdGhlIGZpcnN0LCB0aGUgTi0xdGggZWxlbWVudCB0byB0aGUgc2Vjb25kIGFuZCBzbyBvbiwgaWYgTiBpcyBvZGQgdGhlbiB0aGUgbWlkZGxlIGVsZW1lbnQgaXMgYWRkZWQgdG8gaXRzZWxmLCBmaWd1cmUgMSBpbGx1c3RyYXRlcyB0aGUgZm9sZGluZyBwcm9jZXNzLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5TZXQgTiA9IGNlaWwgKE5cLzIpIGFuZCBnbyB0byBzdGVwIDMuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlRoZSBzZXF1ZW5jZSBub3cgY29udGFpbnMgdHdvIG51bWJlcnMsIGlmIHRoZSBmaXJzdCBpcyBncmVhdGVyIHRoYW4gdGhlIHNlY29uZCB0aGVuIEFsaWNlIHdpbnMsIG90aGVyd2lzZSBCb2Igd2lucy48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZvbGQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIwMXB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NDk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIDEuYSBCZWZvcmUgRm9sZGluZyZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2ZvbGQyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEzM3B4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MzI3cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIDEuYiBBZnRlciBvbmUgc3RlcCBvZiBmb2xkaW5nJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvZm9sZDMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTI0cHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDozNzZweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS5jIEFmdGVyIHR3byBzdGVwcyBvZiBmb2xkaW5nLCBBbGljZSB3aW5zISZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHByb2JsZW0geW91JnJzcXVvO3JlIGdpdmVuIHRoZSBzZXF1ZW5jZSBvZiBOIGludGVnZXJzIGFuZCBhcmUgYXNrZWQgZGV0ZXJtaW5lIHRoZSBjb250ZXN0IHdpbm5lciB1c2luZyB0aGUgc2VxdWVuY2UgZm9sZGluZyB0aWUgYnJlYWtlciB0ZWNobmlxdWUuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBUICgxICZsdDs9IFQgJmx0Oz0gMTAwKSwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGUgZmlyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBhbiBpbnRlZ2VyICgyICZsdDs9IE4gJmx0Oz0gMTAwKSwgdGhlIG51bWJlciBvZiBlbGVtZW50cyBvZiB0aGUgc2VxdWVuY2UuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgTiBzcGFjZSBzZXBhcmF0ZWQgaW50ZWdlcnMuIFRoZSBzdW0gb2YgYW55IHN1YnNldCBvZiB0aGUgbnVtYmVycyBmaXQgaW4gYSAzMiBiaXQgc2lnbmVkIGludGVnZXIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIHByaW50IHRoZSBuYW1lIG9mIHRoZSB3aW5uZXIuIEZvbGxvdyB0aGUgb3V0cHV0IGZvcm1hdCBiZWxvdy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d