스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Grupp | Poäng | Gränser |
|---|---|---|
| 1 | 20 | N ≤ 1 |
| 2 | 20 | N ≤ 2 |
| 3 | 30 | N ≤ 5 |
| 4 | 30 | Inga ytterligare begränsningar. |
Förklaring av exempelfall 1
En optimal strategi är följande:
- 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.
- 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.
- 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