시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 30 | 7 | 6 | 21.429% |
캐슬은 가로 거리와 세로 거리 중 최댓값이 2인 칸으로 이동할 수 있는 변형 체스말이다. 아드리아나와 베아트리체는 가로 거리와 세로 거리 중 최댓값이 k인 칸으로 이동할 수 있는 k-캐슬을 사용한 게임을 하고자 한다.
가로 길이와 세로 길이가 모두 1015인 체스판이 있다. 체스판에서 왼쪽에서 x 번째 열과 위쪽에서 y 번째 행이 만나는 칸을 좌표를 사용해서 (x, y)로 표기한다. 게임에 사용할 말은 총 N 개가 있고, 각각 1 번부터 N 번까지의 번호가 붙어있다. i 번 말(1 ≤ i ≤ N)은 ki-캐슬이고, 각 게임이 시작할 때 i 번 말을 체스판에 올려놓는 경우 맨 처음에 (xi, yi)에 올려놓는다.
아드리아나와 베아트리체는 총 N 번의 게임을 할 예정인데, j 번째 게임(1 ≤ j ≤ N)에서는 1 번 말부터 j 번 말까지 총 j 개의 말을 체스판에 올려놓고 게임을 한다.
각 게임은 아드리아나가 먼저 시작해서 아드리아나와 베아트리체가 번갈아가면서 진행한다. 각 사람의 차례마다 다음과 같은 행동을 해야 한다.
* 체스판 위에 있는 말을 하나 골라서 이동시킨다. 이때, (1, 1)과의 ”맨해튼 거리”가 감소해야 한다. 두 좌표 중 커지는 좌표가 있을 수 있음에 주의해야 한다. 즉, i 번 말을 골라서 (x, y)에서 (x', y')로 이동시킨다 하면 max (| x − x' | , | y − y' |) = 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
”를 큰따옴표 없이 출력한다.
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
Adriana Beatrice Adriana Beatrice Adriana Beatrice Adriana Adriana Adriana Adriana Adriana Beatrice Adriana Adriana
University > 서울대학교 > 2022 서울대학교 프로그래밍 경시대회 > Division 1 (Open Contest) K번