Sentlərin qənaəti
Regional yarışmaya, məsələn, NWERC üçün hazırlıq tələb olunur: otaqların və kompüterlərin təşkili, yaxşı tapşırıq dəstinin yaradılması, iştirakçıların dəvət edilməsi, köynəklərin dizaynı, otel otaqlarının rezervasiyası və s. Mən supermarketdə alış-verişə cavabdehəm.
Kassaya çatanda, bütün n əşyalarımı konveyerə qoyuram və məndən əvvəl növbədə olan bütün digər müştərilərin xidmət edilməsini gözləyirəm. Gözləyərkən başa düşürəm ki, bu supermarket son zamanlarda alış-verişin ümumi qiymətini 10 sentin ən yaxın qatına yuvarlamağa başlayıb (əgər 5 sentdirsə, yuxarıya yuvarlanır). Məsələn, 94 sent 90 sentə, 95 sent isə 100 sentə yuvarlanacaq.
Alış-verişimi qruplara bölüb ayrı-ayrılıqda ödəyə bilərəm. d ayırıcı tapıb alış-verişi d + 1 qrupa bölə bildim. Ayırıcıları harada yerləşdirmək lazım olduğunu bilmək istəyirəm ki, bütün alış-verişlərin ümumi dəyərini minimuma endirim. Vaxtım azaldığı üçün lentdəki əşyaları yenidən düzəltmək istəmirəm.
Giriş Məlumatları
Bunlardan ibarətdir:
bir sətir iki ədəd n (1 ≤ n ≤ 2000) və d (1 ≤ d ≤ 20) - alış-verişlərin sayı və mövcud ayırıcıların sayı;
bir sətir n tam ədəd
p[1], ...,p[n](1 ≤p[i]≤ 10000 üçün 1 ≤ i ≤ n) - alış-verişlərin sentlərlə qiymətləri. Qiymətlər lentdəki alış-verişlərin yerləşdiyi ardıcıllıqla verilir.
Çıxış Məlumatları
d ayırıcıdan istifadə edərək bütün məhsulları almaq üçün lazım olan ən az miqdarda pulu çıxarın.