루미 알고리즘

#1409실버Cherimoyor

PO 2016 학교 예선코딩출제 Arash Rouhani스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Farah älskar den exotiska cherimoya-frukten. Eftersom den kommer från ett fjärran land så säljs den bara en dag om året i Sverige! Farah har givetvis passat på att köpa några Cherimoyor just denna dag.

Cherimoyorna är olika mogna. Vissa har precis blivit mogna samma dag medan en del blir ätmogna senare.

Mer precist är det under totalt 3 dagar varje cherimojafrukt är ätmogen. Vi säger att frukten blir ätmogen den dagen. Före kan man inte äta den och efter de tre dagarna måste den slängas.

Farah vill få ut så mycket som möjligt utav cherimoyasäsongen. Hon vill maximera njutningen, njutning räknas ut såhär: För en given dag så får hon 10 njutningspoäng för den första cherimoyan, därefter 9 för den andra, 8 för den tredje o.s.v. Hon orkar aldrig äta mer än 10 Cherimoyor på en dag.

Skriv ett program som givet hur många cherimoyor som blir ätmogna varje dag, avgör hur mycket njutningspoäng Farah kommer att få ut under årets cherimoyasäsong.

Indata

Den första raden av indata innehåller heltalet N (1 ≤ N ≤ 15), antalet dagar som cherimoyorna kan bli mogna på.

För varje av de kommande N dagarna får du ett heltal C_i (0 ≤ C_i ≤ 30), vilket betyder att C_i stycken cherimoyor blir mogna den dagen. Det är då alltså under N+2 dagar som det är aktuellt att äta cherimoyor.

Utdata

Skriv ut ett heltal: hur mycket njutningspoäng Farah som mest kan få med den bästa ätstrategin.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

GruppPoängGränser
120N ≤ 1
220N ≤ 2
330N ≤ 5
430Inga ytterligare begränsningar.

Förklaring av exempelfall 1

En optimal strategi är följande:

  1. Av de 18 cherimoyorna som mognar dag 1, ät 6st på dag 1, 2 och 3. Detta ger 10+9+8+7+6+5=45 njutningspoäng vardera av dagarna.
  2. Av de 2 cherimoyorna som mognar dag 2, ät en på dag 4 och en på dag 5. Detta ger 10 njutningspoäng vardera av dagarna.
  3. Sammanlagt ger detta 45*3+10*2=155 njutningspoäng. Det finns ingen strategi som ger mer njutningspoäng.

예제

예제 1

입력
3
18 0 2
출력
155

예제 2

입력
8
3 0 1 2 0 0 3 6
출력
144

예제 3

입력
2
30 30
출력
220

출처 표기

출처: Programmeringsolympiaden 2016년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.