센티와 마법의 뿅망치

시간 제한1초메모리 제한1024 MB

요약

가장 키가 큰 거인을 매번 2로 나눈 몫으로 줄이되(1이면 그대로) 최대 T번까지 시행한다. 모든 거인이 센티보다 작아지는지 판정하고, 가능하면 최소 사용 횟수를, 불가능하면 시행 후 가장 큰 거인의 키를 출력한다.

난이도: 보통10점 중 6점
유형: 힙, 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

센티는 마법 도구를 지니고 여행하는 것을 취미로 삼는 악당이다.

거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인이 있다는 사실이 마음에 들지 않았다.

센티가 꺼내 든 마법 도구는 마법의 뿅망치다. 이 뿅망치에 맞은 사람의 키는 $\lfloor$ 뿅망치에 맞은 사람의 키 $/\ 2 \rfloor$ 로 변한다. 단, 키가 1인 경우에는 더 줄어들 수 없어 뿅망치의 영향을 받지 않는다.

하지만 마법의 뿅망치에는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 세웠다. 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.

센티가 세운 전략대로 마법의 뿅망치를 사용한다면 거인의 나라의 모든 거인을 센티보다 키가 작게 만들 수 있을까?

입력

첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 $N$ ( $1 \le N \le 10^5$ )과 센티의 키를 나타내는 정수 $H_{centi}$ ( $1 \le H_{centi} \le 2 \times 10^9$ ), 마법의 뿅망치의 횟수 제한 $T$ ( $1 \le T \le 10^5$ )가 빈칸을 사이에 두고 주어진다.

두 번째 줄부터 $N$ 개의 줄에 각 거인의 키를 나타내는 정수 $H$ ( $1 \le H \le 2 \times 10^9$ )가 주어진다.

출력

마법의 뿅망치를 센티의 전략대로 사용하여 거인의 나라의 모든 거인을 센티보다 키가 작게 만들 수 있는 경우, 첫 번째 줄에 YES를 출력하고 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.

마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 사용하고도 거인의 나라에 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.

예제4

예제 1
입력
```
1 10 1
20
```
예상 출력
```
NO
10
```
예제 2
입력
```
2 10 3
16
32
```
예상 출력
```
YES
3
```
예제 3
입력
```
2 10 3
127
8
```
예상 출력
```
NO
15
```
예제 4
입력
```
1 1 100000
1
```
예상 출력
```
NO
1
```