가지 부수기
면접 대비시간 제한1초메모리 제한512 MB
길이 n인 막대기를 두 사람이 번갈아 정수 길이의 두 조각으로 자르고, 마지막으로 자른 사람이 이긴다. 승자를 판정하고 앨리스가 이길 경우 첫 수를 출력한다.
문제
부모님이 일요일 하루 종일 네이메헌 근처의 무커르하이더를 산책하는 것이 "재미있을" 것이라고 결정하셨다.
머릿속으로 프로그래밍 문제를 풀면서 시간을 보낼 수 있는 너와 달리, 동생들은 그럴 여유가 없다. 얼마 지나지 않아 여동생 Alice와 형 Bob은 지독하게 지루해진다. 둘은 함께 게임을 하면서 시간을 보낼 수 있을지 고민한다(이 문제는 나중에 Bob and Alice Pastime Conundrum이라고 불리게 된다). 마침내 둘은 다음과 같은 간단한 게임을 떠올린다.
길이가 n인 가지 하나를 찾아 게임의 주요 대상으로 삼는다. Alice와 Bob은 번갈아 가며 가지의 한 조각을 골라 두 조각으로 부순다. 이때 두 조각의 길이는 모두 정수여야 한다. 마지막으로 조각 하나를 부술 수 있었던 사람이 이긴다. 둘 중 어린 Alice가 먼저 시작한다.
물론 너는 이미 머릿속으로 게임을 다 파악했다. Bob이 최적으로 플레이한다고 가정할 때, Alice가 이길 수 있는가? 이길 수 있다면 첫 번째로 어떤 수를 두어야 하는가?
입력
- 한 줄에 정수 2 ≤ n ≤ 10^9가 주어진다. 이는 가지의 길이이다.
출력
- 첫 번째 줄에 이기는 사람의 이름 Alice 또는 Bob을 출력한다.
- Alice가 이길 수 있다면, Alice가 이기는 수로 부러뜨릴 수 있는 가지 조각의 길이를 출력한다. 이 값은 1 이상 n − 1 이하의 정수여야 한다.
유효한 답이 여러 개라면 아무거나 하나를 출력해도 된다.