Bob부 멍충이

시간 제한1초메모리 제한512 MB

요약
서로 다른 양의 정수를 어떻게 배열해야 게임이 끝나기 전 모든 순간에 Alice의 점수가 Bob의 점수보다 항상 큰지 판별한다.
난이도

보통10점 중 6점

유형
그리디, 정렬
정답자
아직 제출이 없습니다

문제

Alice와 Bob이 길이가 NN인 서로 다른 양의 정수로 이루어진 수열 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots , A\_N에서 게임을 진행한다. 현재 수열에 남은 원소의 개수가 짝수라면, Alice의 점수가 A_1A\_1만큼 증가하고, 홀수라면 Bob의 점수가 A_1A\_1만큼 증가한다. 이후 수열에서 A_1A\_1은 제거된다. 수열이 비게 되면 게임이 종료된다.

게임을 시작하기 전을 제외한 모든 순간에 Alice의 점수가 Bob의 점수보다 크다면 Alice가 이긴다. 그렇지 않은 순간이 한 번이라도 존재하면 Bob이 이긴다. 이때, 배열을 적절하게 섞어서 Alice가 이길 수 있는지 알아보자.

입력

첫째 줄에 수열 AA의 크기 NN이 주어진다. (1≤N≤105)(1 \le N \le 10^5)

둘째 줄에 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots , A\_N이 공백으로 구분되어 주어진다. (1≤A_i≤109)(1 \le A\_i \le 10^9)

A_iA\_i는 서로 다르며, 입력으로 주어지는 모든 수는 정수이다.

출력

Alice가 이길 수 있도록 배열을 섞을 수 있는 경우 Alice를, 그렇지 않은 경우 Bob을 출력한다.

예제1

  1. 예제 1

    입력
    4
    1 2 3 4
    
    예상 출력
    Alice