2회 문제풀이 11 / ABC 138 C - Alchemist
ABC 138 C - Alchemist
【문제 개요】
당신은 냄비와 N개의 재료를 가지고 있습니다. 각 재료는 실수의 값의 가격을 가지고 있으며 i개째의(1 ≦ i ≦ N) 재료의 가격은 vi입니다.
2개의 재료를 냄비에 넣으면, 그것들은 사라지고 새로운 1개의 재료가 생성됩니다. 이 새로운 재료의 가치는 만들때 넣은 2개의 재료의 가격이 x, y일때 (x + y)/2이고 이 재료를 다시 냄비에 넣을수도 있습니다.
이런 합성을 N - 1회 하는것으로 최후의 1개의 재료가 남았습니다. 이 재료의 가격이 될 수 있는 최대치를 구하시오.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 50
- 1 ≦ vi ≦ 1000
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
2
N
v1 v2 ... vN
【출력 형태】
최후에 남을 1개의 재료의 가격이 될 수 있는 최대값을 나타내는 소수 (또는 정수)를 출력하십시오. 출력은 절대 오차 혹은 상대 오차가 10^(-5)이하라면 정답으로 판정된다.
【예시】
입력 예 1
1
2
2
3 4
출력 예 1
1
3.5
처음에 가지고있는 재료 2개의 경우 그대로 넣을 수 밖에 없다. 가치 3, 4의 재료로 합성된 재료의 가치는 (3 + 4)/2 = 3.5입니다. 또한, 3.50001 또는 3.49999으로 출력해도 정답이다.
입력 예 2
1
2
3
500 300 200
출력 예 2
1
375
입력에는 처음에 3개의 재료를 가지고 있으며 어떤 순서로 냄비에 넣을지 선택의 여지가 있습니다. 선택지는 다음과 같습니다.
- 가치 500, 300의 재료를 넣고 가치 (500 + 300) / 2 = 400 의 재료를 만들어낸다. 그 후, 200의 재료와 합성하여 가치 (400 + 200)/2 = 300의 재료를 만들어 낸다.
- 가치 500, 200의 재료를 넣고 가치 (500 + 200) / 2 = 350 의 재료를 만들어낸다. 그 후, 300 재료와 합성하여 가치 (350 + 300)/2 = 325의 재료를 만들어 낸다.
- 가치 300, 200의 재료를 넣고 가치 (300 + 200) / 2 = 250 의 재료를 만들어낸다. 그 후, 500 재료와 합성하여 가치 (250 + 500)/2 = 375의 재료를 만들어 낸다. 위와 같이, 마지막 선택지의 결과인 375가 최대값입니다. 또한 375.0으로 출력해도 정답으로 간주됩니다.
입력 예 3
1
2
5
138 138 138 138 138
출력 예 3
1
138
ABC 138 C - Alchemist
【문제 개요】
당신은 냄비와 N개의 재료를 가지고 있습니다. 각 재료는 실수의 값의 가격을 가지고 있으며 i개째의(1 ≦ i ≦ N) 재료의 가격은 vi입니다.
2개의 재료를 냄비에 넣으면, 그것들은 사라지고 새로운 1개의 재료가 생성됩니다. 이 새로운 재료의 가치는 만들때 넣은 2개의 재료의 가격이 x, y일때 (x + y)/2이고 이 재료를 다시 냄비에 넣을수도 있습니다.
이런 합성을 N - 1회 하는것으로 최후의 1개의 재료가 남았습니다. 이 재료의 가격이 될 수 있는 최대치를 구하시오.
힌트 : 이진 탐색 알고리즘
【전제】
- 2 ≦ N ≦ 50
- 1 ≦ vi ≦ 1000
- 입력받을 모든 수는 정수이다.
【입력 형태】
1
2
N
v1 v2 ... vN
【출력 형태】
최후에 남을 1개의 재료의 가격이 될 수 있는 최대값을 나타내는 소수 (또는 정수)를 출력하십시오. 출력은 절대 오차 혹은 상대 오차가 10^(-5)이하라면 정답으로 판정된다.
【예시】
입력 예 1
1
2
2
3 4
출력 예 1
1
3.5
처음에 가지고있는 재료 2개의 경우 그대로 넣을 수 밖에 없다. 가치 3, 4의 재료로 합성된 재료의 가치는 (3 + 4)/2 = 3.5입니다. 또한, 3.50001 또는 3.49999으로 출력해도 정답이다.
입력 예 2
1
2
3
500 300 200
출력 예 2
1
375
입력에는 처음에 3개의 재료를 가지고 있으며 어떤 순서로 냄비에 넣을지 선택의 여지가 있습니다. 선택지는 다음과 같습니다.
- 가치 500, 300의 재료를 넣고 가치 (500 + 300) / 2 = 400 의 재료를 만들어낸다. 그 후, 200의 재료와 합성하여 가치 (400 + 200)/2 = 300의 재료를 만들어 낸다.
- 가치 500, 200의 재료를 넣고 가치 (500 + 200) / 2 = 350 의 재료를 만들어낸다. 그 후, 300 재료와 합성하여 가치 (350 + 300)/2 = 325의 재료를 만들어 낸다.
- 가치 300, 200의 재료를 넣고 가치 (300 + 200) / 2 = 250 의 재료를 만들어낸다. 그 후, 500 재료와 합성하여 가치 (250 + 500)/2 = 375의 재료를 만들어 낸다. 위와 같이, 마지막 선택지의 결과인 375가 최대값입니다. 또한 375.0으로 출력해도 정답으로 간주됩니다.
입력 예 3
1
2
5
138 138 138 138 138
출력 예 3
1
138