루미 알고리즘

#1306골드The Stock Market

PO 2012 온라인 예선코딩영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

Evelina is going to start speculating on the stock market to become rich. She is actually not really interested in economics and never bother to read more than the first stock price in the newspaper. But, she thinks, it's everyone else who is complicating things. If you buy and sell a stock at the right time you could just as well earn money on this one company, which we call A. By always asking her friends about the amount of fish balls they eat she has learned to exactly predict the price of A for the next N days. Write a program that computes the amount of money she has at the end of that period if she starts with 100 SEK and invests optimally. She can never borrow money, she must use her own.

The stock price is updated daily and is the same for both buying and selling stocks. Each day Evelina can either buy any amount of stock, sell any amount of stock or do nothing. The amount she purchases doesn't have to be an integer. For each transaction, she must pay a fixed courtage fee. The fee is paid in cash, that is before she buys stocks she must pay a fee, and after she sells stocks she must pay a fee.

Input

The first line contains the integer N (2 ≤ N ≤ 100000), the number or days.

The second line contains a decimal number Q (0 ≤ Q ≤ 100), the fee in SEK per transaction.

This is followed by N lines each containing a decimal number, the stock price for each day. The price is always between 1 and 1000 SEK.

All decimal numbers have at most 10 digits after the decimal point.

Output

Output the maximum amount of money she can have after N days. Your answer will be considered correct if it has a relative or absolute error of at most 10^-5.

Scoring

Your solution will be tested on a set of test case groups. To get the points for a group, you need to pass all the test cases in the group.

GroupPoint valueConstraints
130N ≤ 14
240N ≤ 1000
330No additional constraints.

예제

예제 1

입력
6
2.3
75.6
86.2
83.1
91.3
72.5
95.7
출력
147.3742063492

출처 표기

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