루미 알고리즘

#1529실버Lava Kayaking

PO 2021 학교 예선코딩출제 Fredrik Ekholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Lav has been captured by an evil witch in a volcano. In the vast lava sea of the volcano, there are N islands in a long row. The distance between the i:th and the (i+1):th island is d_i. The distances are given in the unit ”witchameter,” which corresponds to exactly H meters. The witch lives on the first island in the row, and this is where Lav is currently located.

The witch has forgotten her book with all the spells on the last island in the row, and now forces Lav to go and fetch it. To help him, he has a lava boat and a number of paddles. Each paddle lasts for K paddle strokes, where each stroke moves the boat forward one meter, before the paddle burns up due to the lava. Lav takes a number of paddles from the witch and does not need to completely use up one paddle before switching to another.

Additionally, Lav has a spell from the witch that he can use when he is on an island. The spell repairs a paddle that he has paddled with a bit but hasn't completely burned up. He can then use it again to paddle K meters. Lav can use the spell as many times as he wants when he is on an island.

Write a program that calculates the minimum number of paddles the witch needs to give Lav so that he can complete the mission.

Input

The first line contains the integers N, K, H (1 ≤ N ≤ 20, 1 ≤ K ≤ 15, 1 ≤ H ≤ 10^12), the number of islands, the number of meters you can paddle with a paddle before it burns up, and the number of meters a witchameter corresponds to.

The second line contains N-1 integers d_i (1 ≤ d_i ≤ 1000), the distances between adjacent islands in the row.

Output

Print an integer: the minimum number of paddles the witch needs to give Lav so that he can complete the mission.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

GroupPoint valueConstraints
120K = 1, H ≤ 100
240H = 1
340No additional constraints.

Explanation of samples

In the first example, there are two islands, with a distance of 7 witchameters, which corresponds to 7 · H = 7 · 10=70 meters. With each paddle, he can take a maximum of 5 paddle strokes, so 70/5 = 14 paddles are required.

In the second example, there are three islands, with 200 meters between the first and the second, and 100 meters between the second and the third. Each paddle can take 7 paddle strokes. If Lav starts with 31 paddles, uses 14 of them fully, and takes 6 paddle strokes with the remaining 17 paddles, he will cover 14 · 7+6 · 17=200 meters, enough to reach the second island. Then he has 17 paddles left, which he repairs with the spell, enough to get from the second to the third island. It would not have been possible with fewer than 31 paddles.

예제

예제 1

입력
2 5 10
7
출력
14

예제 2

입력
3 7 100
2 1
출력
31

예제 3

입력
5 15 1000000000000
92 43 89 10
출력
6531851851852

출처 표기

출처: Programmeringsolympiaden 2021년 학교 예선 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.