ez_code   4년 전

문제

남작 코헨 경은 나라에서 가장 아름다운 정원 울타리를 가지고 있습니다. 우승을 한 그의 정원 울타리에는 N개의 아네모네 덤불이 직선을 따라 쭉 심어져 있습니다. 덤불에 왼쪽부터 차례대로 1부터 N번까지 번호를 붙입니다. 남작의 이웃은 모든 덤불의 높이가 같도록 정원 울타리를 다듬어 관리합니다. 하지만 코헨 경에게는 조경 비법이 있습니다. 그의 정원사는 정원 울타리를 다듬을 때 특별한 규칙을 따르는데, 이것이 남작의 정원 울타리가 항상 우승을 하는 이유입니다.

규칙은 다음과 같습니다. - 2번 덤불에서 시작해 오른쪽으로 이동합니다. 정원사는 각 덤불의 높이가 정확히 양 옆 덤불의 평균이 되도록 덤불을 자릅니다. 덤불의 길이가 이미 평균 이하라면 정원사는 이 덤불을 건드리지 않고 다음 덤불로 이동하는데, 이 과정을 끝에서 두 번째 덤불에 이를 때까지 반복합니다. 남작은 이 방법이 조경을 성공하는 방법이라고 확신합니다.

입력

첫 줄에 테스트 케이스의 수 T가 주어집니다. T개의 테스트 케이스가 이어 주어집니다. 각 테스트 케이스는 두 줄로 이루어집니다. 첫 줄은 정수 N, 둘째 줄은 1번부터 N번 덤불의 높이를 나타내는 공백으로 구분된 N개의 정수입니다.

제한

- 1 <= T <= 100

- 각 높이는 1 이상 1000 이하의 정수입니다.

- 3 <= N <= 1000

출력

각 테스트 케이스에 대해, x가 (1부터 시작하는) 테스트 케이스의 번호이고 y가 정원사가 남작의 특별한 방식에 따라 정원 울타리를 다듬었을 때 N-1번 덤불의 높이를 나타내는 "Case #x: y"를 출력합니다.

답이 실제 답과 최대 10 ^ (-4)의 상대 오차를 지닐 경우 정답으로 간주합니다.

댓글을 작성하려면 로그인해야 합니다.