순열 게임 - 2 입력의 경우 - 설명

Question

순열 게임 (30 점)

앨리스와 밥은 다음과 같은 게임 플레이 :

1) 그들은으로 시작하는 최초의 N 번호의 순열을 선택합니다.

2) 그들은 번갈아 재생되며 앨리스가 먼저 재생됩니다.

3) 차례로 나머지 순열을 순열에서 제거 할 수 있습니다.

4) 나머지 숫자가 증가하는 순서로 게임이 끝나면 게임이 종료됩니다. 마지막 턴을 한 사람 (그 이후에 순서가 점점 커짐)이 게임에서 승리합니다.

둘 다 최적으로 플레이한다고 가정 할 때 누가 게임에서 승리합니까?

입력 :
첫 번째 줄에는 테스트 사례 T의 수를 포함합니다. T 테스트 사례가 이어집니다. 각 경우에는 첫 번째 줄에 정수 N이 있고 그 다음에 두 번째 줄에 정수 1..N이 순열됩니다.

출력 :
출력 T 라인, 각 테스트 케이스마다 하나씩, 앨리스가 게임에서 승리하면 "앨리스", 그렇지 않으면 "밥"이 포함됩니다.

구속 :
< 1 = T = 100 <
2 < < = N = 15

순열이 처음 증가하는 순서이어야한다.

시료 입력 :
2
3
1 3 2
5
5 3 2 1 4

샘플 출력 :
앨리스
밥

설명 : 들면 첫 번째 예에서는 Alice가 3 또는 2를 제거하여 시퀀스가 ​​증가하고 게임에서 승리 할 수있게합니다. .

사람이 상기 제 2 입력의 경우에 좀 도와주세요 수 :

가능한 증가 서열 5 3 2 1 4

은 :
1) (3) 4 - 어떤 순서로, 5 2 1 분리
2) 2 4 - 모든 시퀀스

따라서 출력 앨리스 있어야에서 5 3 2 분리 - 모든 시퀀스
3) 1 4 5, 3, 1 분리?

코드를 공유하지 마십시오. 감사합니다

Answer 1

앨리스는 밥이 4을 제거 후 5,3,2,1 중 하나를 제거합니다. 따라서 증가하는 순서는 하나의 요소 일 수 있으며 요소는 임의의 순서로 제거 될 수 있습니다. 따라서 Bob이 이깁니다.

앨리스가 4을 제거하면 증가 시퀀스도 하나의 요소 여야합니다. 밥이 이긴다.

그래서 Bob이 이깁니다.

Answer 2

참고 :이 프로그래밍 문제는 아니며 정말이 사이트에 속하지 않습니다 ...

확실히 앨리스는 두 번째 테스트 케이스의 승자가되어야합니다.

흐름 :

// Start state 
5 3 2 1 4 

// Alice remove 5 
3 2 1 4 

// Bob remove 3, 2, or 1 
(2 1 4) or (3 1 4) or (3 2 4) 

// Alice remove first number remaining 
(1 4) or (2 4) 

// Alice won! 

Answer 3

가능한 경우는 4 수 있습니다 또는 5가 입력 매개 변수로 서열

증가로 간주됩니다 n은> = 2

그러나 앨리스는 최적의 재생 및 당신은 아마해야