만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

감자튀김

시간 제한2초메모리 제한512 MB

요약
무한한 줄에서 P명에게 감자튀김을 하나씩 주고, 매 단계 모두가 가진 감자튀김을 양옆으로 절반씩 나눕니다. T단계 뒤 L개 이상을 가진 사람의 수를 구합니다.
난이도

보통10점 중 7점

유형
확률, 조합론, 수학
정답자
아직 제출이 없습니다

문제

양방향으로 끝없이 이어진 줄에 무한히 많은 사람이 서 있습니다. 이 중 서로 다른 PP명을 골라 각자에게 감자튀김을 하나씩 줍니다. 다소 불공평하므로, 모든 사람이 동시에 자신이 가진 감자튀김을 전부 집어 둘로 나누고, 절반은 왼쪽 사람에게, 나머지 절반은 오른쪽 사람에게 줍니다. 이 과정을 T−1T - 1번 더 반복합니다. TT번의 단계가 끝난 뒤 감자튀김을 LL개 이상 가진 사람은 배가 부릅니다. 배가 부른 사람은 몇 명입니까?

입력

첫째 줄에 두 정수 PP, TT와 실수 LL이 주어집니다 (1≤P≤3×1051 \le P \le 3 \times 10^5, 1≤T≤5×1071 \le T \le 5 \times 10^7, 10−4≤L≤1010^{-4} \le L \le 10). 둘째 줄에는 처음에 감자튀김을 받는 사람들의 번호 PP개가 주어집니다. 번호는 모두 서로 다르며 00 이상 10710^7 이하입니다.

출력

감자튀김을 LL개 이상 가진 사람의 수를 정수 하나로 출력합니다. 답 XX가 0.8L0.8L개 이상 가진 사람의 수와 1.2L1.2L개 이상 가진 사람의 수 사이에 있으면 정답으로 인정합니다.

힌트

첫 번째 예제에서 번호 00과 22인 사람은 각각 감자튀김을 하나씩 가지고 있습니다. 이를 나누어 이웃에게 절반씩 넘기면, 번호 −1-1과 33인 사람은 0.50.5개, 번호 11인 사람은 11개를 가집니다. 배부름 기준은 0.740.74개이므로 배가 부른 사람은 번호 11인 사람 하나뿐입니다. 두 번째 예제에서 답 13은 정확한 값이지만, 12부터 15까지의 출력도 정답으로 인정됩니다.

예제2

  1. 예제 1

    입력
    2 1 0.74
    0 2
    
    예상 출력
    1
    
  2. 예제 2

    입력
    4 100 0.1
    1 2 3 11
    
    예상 출력
    13