| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 245 | 139 | 109 | 55.051% |
우진이는 오늘 아침 $N$개의 식물을 밭에 심었다. $i$번째 식물은 $a_i$일 연속으로 물을 받지 못하면 시들어버리는데, 특이하게도 $a_i$는 2ドル$의 거듭제곱이다.
우진이는 오늘 아침 모든 식물에 물을 주었다. 우진이는 민석이에게 내일부터 매일 아침 $N$개의 식물 중에서 $X$개의 식물에만 물을 주라고 시켰다. 민석이는 모든 식물이 영원히 시들지 않도록 최선을 다해서 $X$개의 식물을 골라 물을 준다.
$X$의 값에 따라 모든 식물이 영원히 시들지 않도록 하는 것이 불가능할 수도 있다. 우진이는 적절한 $X$를 정해서 민석이에게 알려주려고 한다. 민석이가 모든 식물이 영원히 시들지 않도록 할 수 있는 $X$의 최솟값을 구해보자.
첫째 줄에 정수 $N(1\le N\le 100,円 000)$이 주어진다.
둘째 줄에 정수 $a_1,a_2,\cdots ,a_N(1\le a_i\le 2^{16};$ $a_i$는 2ドル$의 거듭제곱$)$이 공백으로 구분되어 주어진다.
민석이가 최선을 다한다면 모든 식물이 영원히 시들지 않도록 할 수 있는 $X$의 최솟값을 구해보자.
4 4 2 2 1
3
$X=3$일 때, 민석이가 모든 식물이 영원히 시들지 않도록 물을 주는 방법 중 하나는 다음과 같다.
민석이가 처음으로 식물에 물을 주는 날을 1ドル$번째 날이라고 할 때, 임의의 양의 정수 $k$에 대해서 다음과 같이 물을 준다.
이 방법 외에도 모든 식물이 영원히 시들지 않도록 하는 방법은 여러 가지가 있지만, $X$가 3ドル$보다 작을 때 모든 식물이 영원히 시들지 않도록 하는 방법은 없다.
2 1 1
2
5 4 16 2 32 8
1
본문의 이미지는 출제자가 직접 그린 동방 프로젝트 2차 창작물입니다.