ملخ سکه ها را جمع آوری می کند
Problem
ملخ بر روی ستون هایی که در یک خط در فواصل مساوی از یکدیگر قرار دارند می پرد. ستون ها دارای شماره سریال از 1 تا N هستند. در ابتدا، ملخ روی یک پست با شماره 1 می نشیند. می تواند از نوارهای 1 به K به جلو بپرد و از نوار فعلی شمارش شود.
در هر ستون، ملخ می تواند چندین سکه طلا به دست آورد یا از دست بدهد (این عدد برای هر ستون مشخص است). تعیین کنید که ملخ چگونه باید بپرد تا بتواند بیشترین سکه های طلا را جمع کند. به خاطر داشته باشید که Grasshopper نمی تواند به عقب بپرد.
ورودی:
- سطر اول شامل دو عدد طبیعی است: N و K (\(2 <= N ,\ K < = 10000\))، با فاصله جدا شده؛
- در خط دوم، اعداد صحیح N-2 با فاصله – تعداد سکه هایی که Grasshopper در هر ستون دریافت می کند، از 2 تا N-1ام. اگر این عدد منفی باشد، Grasshopper سکه ها را از دست می دهد.
تضمین شده است که همه اعداد در مدول از 10000 تجاوز نکنند.
خروجی:
- در خط اول، برنامه باید حداکثر تعداد سکه هایی را که Grasshopper می تواند جمع آوری کند نمایش دهد؛
- خط دوم تعداد پرش های Grasshopper را نشان می دهد؛
- در خط سوم – تعداد تمام ستون های بازدید شده توسط Grasshopper (با یک فاصله به ترتیب صعودی از هم جدا شده اند).
اگر چندین پاسخ صحیح وجود دارد، یکی از آنها را چاپ کنید.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|