확률의 마법사
면접 대비시간 제한2초메모리 제한512 MB
1부터 N까지의 비밀 수를 K번의 참/거짓 질문으로 항상 알아낼 수 있는지 판정한다. K번의 질문으로 구분 가능한 경우는 많아야 2^K가지다.
문제
긴 여행 끝에 확률의 마법사를 만났다. 마법사는 다음 퍼즐을 풀면 소원을 하나 들어주겠다고 약속한다.
마법사는 먼저 두 정수 과 를 알려준다. 그다음 1 이상 이하의 정수를 하나 몰래 고르고, 그 값은 알려주지 않는다.
목표는 이 비밀 숫자를 정확히 맞히는 것이다. 답을 말하기 전에 그 숫자를 두고 참 또는 거짓으로 답이 돌아오는 질문을 번 할 수 있다. 예를 들어 "그 숫자는 짝수입니까", "그 숫자는 7 이상 10 이하입니까", "그 숫자는 17 또는 22입니까", "그 숫자는 소수입니까" 같은 질문이다. 마법사는 언제나 정직하게 참이나 거짓으로 답한다. 질문 개에 모두 답을 받은 뒤에는 숫자를 하나 말해야 한다. 맞히면 소원이 이루어지고, 틀리면 날개 달린 원숭이가 된다.
형식적으로 질문은 집합 에서 참과 거짓 두 값으로 가는 함수이고, 마법사는 자신이 고른 비밀 숫자에서 이 함수가 어떤 값인지 알려준다. 앞선 질문의 답을 본 뒤에 다음 질문을 정해도 된다.
과 가 주어질 때, 마법사가 어떤 숫자를 고르더라도 질문 개만으로 비밀 숫자를 항상 알아낼 수 있는지 판정하라.
입력
첫째 줄에 두 정수 과 가 공백 하나로 구분되어 주어진다. (, )
두 값 모두 64비트 정수 범위를 넘을 수 있다.
출력
항상 이기는 것을 보장할 수 있으면 첫째 줄에 Your wish is granted!를 출력한다. 그렇지 않으면 You will become a flying monkey!를 출력한다. 따옴표는 출력하지 않는다.