감자튀김
시간 제한2초메모리 제한512 MB
무한한 줄에서 P명에게 감자튀김을 하나씩 주고, 매 단계 모두가 가진 감자튀김을 양옆으로 절반씩 나눕니다. T단계 뒤 L개 이상을 가진 사람의 수를 구합니다.
문제
양방향으로 끝없이 이어진 줄에 무한히 많은 사람이 서 있습니다. 이 중 서로 다른 명을 골라 각자에게 감자튀김을 하나씩 줍니다. 다소 불공평하므로, 모든 사람이 동시에 자신이 가진 감자튀김을 전부 집어 둘로 나누고, 절반은 왼쪽 사람에게, 나머지 절반은 오른쪽 사람에게 줍니다. 이 과정을 번 더 반복합니다. 번의 단계가 끝난 뒤 감자튀김을 개 이상 가진 사람은 배가 부릅니다. 배가 부른 사람은 몇 명입니까?
입력
첫째 줄에 두 정수 , 와 실수 이 주어집니다 (, , ). 둘째 줄에는 처음에 감자튀김을 받는 사람들의 번호 개가 주어집니다. 번호는 모두 서로 다르며 이상 이하입니다.
출력
감자튀김을 개 이상 가진 사람의 수를 정수 하나로 출력합니다. 답 가 개 이상 가진 사람의 수와 개 이상 가진 사람의 수 사이에 있으면 정답으로 인정합니다.
힌트
첫 번째 예제에서 번호 과 인 사람은 각각 감자튀김을 하나씩 가지고 있습니다. 이를 나누어 이웃에게 절반씩 넘기면, 번호 과 인 사람은 개, 번호 인 사람은 개를 가집니다. 배부름 기준은 개이므로 배가 부른 사람은 번호 인 사람 하나뿐입니다. 두 번째 예제에서 답 13은 정확한 값이지만, 12부터 15까지의 출력도 정답으로 인정됩니다.