난쿤이와 란이는 친구들을 모아 UP&DOWN 게임을 하려 한다. UP&DOWN 게임이란, 1~N까지의 숫자 중에 서 난쿤이가 숫자 하나를 생각하면, 란이와 친구들이 그 숫자를 맞추는 것이다. 만약, 숫 자가 틀렸다면 난쿤이는 그 숫자보다 큰지 작은지를 말해준다. 란이와 친구들이 차례로 숫자를 불러 한바퀴가 넘어가게 되면 난쿤이 가 이기고, 그 전에 맞추면 난쿤이가 지게 된다.
난쿤이에게 당하기만 한 란이는 난쿤이가 무 조건 지도록 사람들을 불러오려 한다. 하지 만, 너무 많은 사람들을 데려오면 난쿤이가 수상한 것을 눈치채고 게임을 하려 하지 않 을 것이므로, 난쿤이를 이기기 위한 최소한 의 사람 수를 모으려 한다. (N이 16인데 16 명이서 게임을 한다면 당연히 난쿤이가 질 것이다.)
모든 친구들이 난쿤이가 지도록 최선을 다해 게임을 한다 가정할 때, 최소 몇 명이 모여 야 난쿤이를 이길 수 있을지 알려주도록 하 자. 입력 형식 출력 형식 입력과 출력의 예
입력 3 출력 1 입력 5 출력 2
출처:algolab.org