시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB307621.429%

문제

캐슬은 가로 거리와 세로 거리 중 최댓값이 2인 칸으로 이동할 수 있는 변형 체스말이다. 아드리아나와 베아트리체는 가로 거리와 세로 거리 중 최댓값이 k인 칸으로 이동할 수 있는 k-캐슬을 사용한 게임을 하고자 한다.

가로 길이와 세로 길이가 모두 1015인 체스판이 있다. 체스판에서 왼쪽에서 x 번째 열과 위쪽에서 y 번째 행이 만나는 칸을 좌표를 사용해서 (x, y)로 표기한다. 게임에 사용할 말은 총 N 개가 있고, 각각 1 번부터 N 번까지의 번호가 붙어있다. i 번 말(1 ≤ iN)은 ki-캐슬이고, 각 게임이 시작할 때 i 번 말을 체스판에 올려놓는 경우 맨 처음에 (xi, yi)에 올려놓는다.

아드리아나와 베아트리체는 총 N 번의 게임을 할 예정인데, j 번째 게임(1 ≤ jN)에서는 1 번 말부터 j 번 말까지 총 j 개의 말을 체스판에 올려놓고 게임을 한다.

각 게임은 아드리아나가 먼저 시작해서 아드리아나와 베아트리체가 번갈아가면서 진행한다. 각 사람의 차례마다 다음과 같은 행동을 해야 한다.

* 체스판 위에 있는 말을 하나 골라서 이동시킨다. 이때, (1, 1)과의 ”맨해튼 거리”가 감소해야 한다. 두 좌표 중 커지는 좌표가 있을 수 있음에 주의해야 한다. 즉, i 번 말을 골라서 (x, y)에서 (x', y')로 이동시킨다 하면 max (| xx' | , | yy' |) = ki이고 x' + y' < x + y이어야 한다.

각 게임에 대해서 더 이상 말을 이동시킬 수 없는 사람이 지게 된다.

두 개 이상의 말이 하나의 칸에 동시에 있을 수 있다.

아드리아나와 베아트리체 두 사람이 모두 각 게임을 최선을 다해서 진행한다고 할 때, 각 게임의 이기는 사람을 예측해 보자.

입력

첫째 줄에는 N이 주어진다. (1 ≤ N ≤ 3 × 105)

둘째 줄부터 N 개의 줄에 1 번 말부터 N 번 말까지 ki, xi, yi가 주어진다. (1 ≤ ki ≤ 107, 1 ≤ xi, yi ≤ 1015)

출력

첫째 줄부터 N 개에 줄에 1 번째 게임부터 N 번째 게임까지 각 게임에 대해 아드리아나가 이기면 “Adriana”를, 베아트리체가 이기면 “Beatrice”를 큰따옴표 없이 출력한다.

예제 입력 1

14
10 37 61
5 72 66
10 39 48
9 143 135
10 19 21
10 21 16
9 73 50
5 20 13
9 50 20
10 76 62
5 36 11
7 130 123
5 26 41
8 89 88

예제 출력 1

Adriana
Beatrice
Adriana
Beatrice
Adriana
Beatrice
Adriana
Adriana
Adriana
Adriana
Adriana
Beatrice
Adriana
Adriana

출처

University > 서울대학교 > 2022 서울대학교 프로그래밍 경시대회 > Division 1 (Open Contest) K번

  • 문제를 만든 사람: sait2000
  • 문제를 검수한 사람: 윤지학