JOI 2012/2013 Spring- 케이크 나누기(cake) > 문제은행 : 정보올림피아드&알고리즘




2808 : 케이크 나누기(cake)

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
6 회   
시도횟수
37 회   

문제

 상현이의 취미는 과자와 빵을 만드는 것이다. 오늘은 큰 맘 먹고 케익을 만들었다. 친구 형돈이가 놀러 와 있기 때문이다.

아래 그림처럼 케이크는 원형이다. N개의 조각으로 나누고 한 지점에서 시작하여 시계 반대 방향으로 번호를 붙였는데 우연히도 모두 다른 크기가 되었다.

 

 

 

이렇게 나누어진 N개의 케이크를 상현이와 형돈이는 나누어 먹기로 하였다. 나누어 먹는 방법은 아래와 같다.

 

- 손님인 형돈이가 먼저 선택한다.

- 이후 상현이와 형돈이가 번갈아 가며 케이크를 선택한다.

- 첫 조각을 형돈이가 선택한 후 상현이가 선택하는데 케이크가 무너지는 것을 방지하기 위하여 형돈이가 선택한 조각의 양쪽 조각중에서 큰 것을 선택한다.

 

위 그림의 예를 들면 형돈이가 1번 조각을 선택한 경우, 상현이는 2번, 5번 중에서 5번을 선택한다. 다음 형돈이는 2번 4번 중에 4번을 선택한다. 다시 상현이는 2번 3번 중에서 2번을 선택한다. 형돈이는 남은 3번 조각을 선택한다.

 

따라서 형돈이가 1번 조각을 첫 조각으로 선택한 경우 형돈이는 2 + 10 + 1 = 13 크기의 케이크를 먹게 된다. 형돈이는 문득 각 조각에 대해 그 조각을 첫 조각으로 선택할 때 먹게 되는 케이크의 전체 양이 궁금해졌다.

 

과제

 

케이크 조각의 수 N과 N개의 케이크 조각에 대한 크기의 정보가 주어질 때, 각 조각에 대하여 그 조각을 형돈이가 첫 조각으로 선택할 때 먹게 되는 케이크의 전체 양을 구하는 프로그램을 작성하시오.


입력형식

첫 행에 케이크 조각의 개수 N이 주어진다. 다음 행에서부터 N개의 행에 걸쳐 각 케이크 조각의 크기 Ak ( 1 <= k <= N)가 주어진다. 제한 조건 2 <= N <= 300,000 1 <= Ak <= 1,000,000,000 (1 <= k <= N). 입력 데이터의 10점에 대하여 N <= 5,000 이다. 입력 데이터의 90점에 대하여 추가적인 제한 조건이 없다.

출력형식

N개의 각 조각에 대하여 그 조각을 형돈이가 첫 조각으로 선택할 때 먹게 되는 케이크의 전체 양을 구하는 프로그램을 작성하시오.

입력 예

5
2
8
1
10
9

출력 예

13
18
12
13
12

Hint!

1번 조각(크기 2)을 형돈이가 선택한 경우 형돈 1번 조각(크기 2) 상현 5번 조각(크기 9) 형돈 4번 조각(크기 10) 상현 2번 조각(크기 8) 형돈 3번 조각(크기 1) 따라서 2+10+1 = 13이 된다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP