15871번 - French Fries 서브태스크스페셜 저지다국어

An infinite number of people are standing in a line, which extends infinitely to both left and right. P different people are selected to get one French fry each. Since this is somewhat unfair, everybody simultaneously takes all their French fries and split them in two, giving half to the person on the left and half to the person on the right. Then they repeat this, for T − 1 more time steps. If a person after these T time steps has at least L French fries (where L is not necessarily an integer), they will be full. How many people will become full?

The first line of input contains the two integers P and T (1 ≤ P ≤ 3 · 10⁵, 1 ≤ T ≤ 5 · 10⁷), and the floating point number L (10⁻⁴ ≤ L ≤ 10). The second line of input contains P distinct integers: the indices of the people who initially get French fries. All indices of people will be between 0 and 10⁷.

Print one integer: the number of people who will end up with at least L fries.

An answer X will be treated as correct if it is between the number of people who get at least 0.8L fries, and the number who get at least 1.2L fries.

• P ≤ 100
• T ≤ 100
• all initial indices are between 0 and 100

• P ≤ 500
• T ≤ 100

• P ≤ 3 · 10⁵
• T ≤ 100

• P ≤ 100
• T ≤ 10⁵

• P ≤ 500
• T ≤ 5 · 10⁷

• P ≤ 3 · 10⁵
• T ≤ 5 · 10⁷

In the first example, the people at indices 0 and 2 initially have one French fry each. After they split these into two and give half to their neighbors, the people at indices −1 and 3 will have 0.5 fries, while the person at index 1 will have 1. The limit for becoming full is 0.74 French fries; thus, person 1 is the only one who gets full.

In the second example, the answer 13 is accurate, but any output between 12 and 15 would be accepted