시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 54 21 19 43.182%

문제

당근을 잘 볶으려면 당근의 크기를 모두 비슷하게 만들고 볶아야 한다. 

상근이는 당근 N개를 가지고 있다. 상근이는 한 번에 당근 하나를 칼로 두 조각으로 낼 수 있다. 즉, 무게가 w인 당근을 잘라서 무게가 wleft와 wright인 두 당근을 만들 수 있다. (wleft + wright = w) 

상근이는 칼질을 무서워하기 때문에, 칼질을 되도록 적게 하려고 한다.

당근의 무게가 주어졌을 때, 가장 가벼운 당근과 큰 무거운 당근의 무게의 비율이 T를 넘기 위한 최소 칼질 횟수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 비율 T와 당근의 수 N이 주어진다. T는 소수점 둘째 자리까지 주어지며, 0.5 < T < 1을 만족한다. N은 양의 정수이며,  N ≤ 1,000이다.

둘째 줄에는 당근의 무게 w1, w2, ..., wN이 주어진다. wi는 106보다 작은 양의 정수이다.

출력

첫째 줄에 가장 가벼운 당근과 가장 무거운 당근의 비율이 T를 넘기 위해 필요한 칼질의 최소 횟수를 출력한다. 정답은 항상 500보다 작다.

소수점 오차로 인해서 생기는 오답을 막기 위해 비율이 T + 0.0001라고 풀었을 때의 정답과 T라고 풀었을 때의 정답이 같은 입력만 주어진다.

예제 입력

0.80 2
1000 1400

예제 출력

3

예제 입력 2

0.99 3
2000 3000 4000

예제 출력 2

6

힌트