Problem
Çekirge, aynı hat üzerinde birbirinden eşit uzaklıkta bulunan sütunların üzerine atlar. Sütunlar, 1 ile N arasında seri numaralarına sahiptir. Başlangıçta, Çekirge 1 numaralı bir gönderinin üzerinde oturuyor. Geçerli olandan sayarak 1'den K çubuklarına atlayabilir.
Her sütunda, Çekirge birkaç altın para kazanabilir veya kaybedebilir (bu sayı her sütun için bilinir). Çekirgenin en çok altını toplamak için nasıl zıplaması gerektiğini belirleyin. Grasshopper'ın geriye doğru zıplayamayacağını unutmayın.
Giriş:
- ilk satır iki doğal sayı içerir: N ve K (\(2 <= N ,\ K < = 10000\)), boşlukla ayrılmış;
- ikinci satırda boşlukla ayrılmış N-2 tamsayıları – Grasshopper'ın 2.'den N-1'e kadar her sütunda aldığı jeton sayısı. Bu sayı negatifse Çekirge jeton kaybeder.
Modulo'daki tüm sayıların 10000'i geçmemesi garanti edilir.
Çıktı:
- ilk satırda, programın Çekirge'nin toplayabileceği maksimum para sayısını göstermesi gerekir;
- ikinci satır Grasshopper'ın atlama sayısını gösterir;
- üçüncü satırda – Çekirge tarafından ziyaret edilen tüm sütunların sayısı (artan sırada bir boşlukla ayrılmış).
Birden fazla doğru yanıt varsa, herhangi birini yazdırın.
Örnekler
| # |
Girdi |
Çıktı |
| 1 |
5 3
2 -3 5
|
7
3
1 2 4 5
|