프로그래머와 돌

시간 제한2초메모리 제한2048 MB

요약

두 사람이 번갈아 가며 비어 있지 않은 더미 중 일부를 골라 각 더미에서 돌을 하나씩 뺍니다. 최적으로 둘 때 누가 이기는지 구합니다.

난이도: 보통10점 중 5점
유형: 게임 이론, 수학
정답자: 아직 제출이 없습니다

문제

프로그래머 Alice와 Dmitry가 새로운 게임을 만들었다. 이 게임에서는 탁자 위에 $n$ 개의 돌 더미가 있다. 두 플레이어는 Alice부터 번갈아 가며 차례를 진행한다. 자기 차례에 플레이어는 비어 있지 않은 더미들로 이루어진 임의의 비어 있지 않은 집합을 고르고, 그 집합에 속한 각 더미에서 돌을 하나씩 제거한다. 움직일 수 없는 플레이어가 진다. 두 플레이어가 최선을 다할 때 누가 이기는가?

입력

첫 번째 줄에 정수 $n$ ( $1 \le n \le 100\,000$ )이 주어진다. 두 번째 줄에는 $n$ 개의 수 $a_1, a_2, \ldots, a_n$ 이 주어진다. 이는 각 돌 더미의 초기 개수이다 ( $1 \le a_i \le 10^9$ ).

출력

Alice 또는 Dmitry 중 게임에서 이기는 사람의 이름을 출력한다. 이름의 대소문자는 구분한다.

예제2

예제 1
입력
```
5
1 2 3 4 5
```
예상 출력
```
Alice
```
예제 2
입력
```
2
2 2
```
예상 출력
```
Dmitry
```