Simulare OJI 2007 clasa a 8-a | afise

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s Memory limit: 2MB Input: afise.in Output: afise.out

Campania electorală s-a terminat de mult, dar zidul din parcul central al orașului în care au fost puse afișele este încă într-o formă dezolantă. Ploile și vântul au acționat și au urâțit și mai mult această zonă pe care altă dată erau afișe frumos colorate. Primăria a decis să se ocupe de această problemă. A format o comisie și a decis realizarea unor panouri reclamă care să ascundă porțiunile deteriorate.

Deoarece fondurile sunt mici s-a decis să fie alocate doar un anumit număr de panouri publicitare care trebuie să ocupe o suprafață cât mai mică posibil. Comisia a primit datele din teren sub forma: lungime zid, câte unități sunt ocupate cu afișe ce trebuie acoperite și care este numărul de panouri pe care le poate folosi. De asemenea se primesc ca date și care sunt unitățile de zid ocupate cu afișe deja deteriorate.

Cerință

Fiind date lungimea zidului, câte unități sunt deteriorate, care este numărul maxim de panouri ce pot fi folosite și care sunt unitățile de zid deteriorate, se cere să se determine lungimea minimă totală a panourilor care sunt folosite pentru a acoperi zona și câte panouri se folosesc. Lungimea minimă o definim ca numărul total de unități de zid acoperite astfel încât să fie mascate zonele problemă. Pentru acoperirea unităților de zid deteriorate, nu este neapărat necesar să se folosească toate panourile. Numărul de panouri folosite fiind limitat există posibilitatea să fie acoperite și zone din zid care sunt curate.

Date de intrare

Fișierul de intrare afise.in conține pe prima linie 33 valori separate prin câte un spațiu L n kL \ n \ k, cu semnificația: LL lungimea totală a zidului, nn numărul de unități ce urmează a fi acoperite și kk numărul maxim de panouri ce pot fi folosite. Pe a doua linie separate prin câte un spațiu sunt nn valori x1,x2,,xnx_1, x_2, \dots, x_n, unde xi reprezintă unitatea din zid care este acoperită de un afiș vechi. Valorile x1,x2,,xnx_1, x_2, \dots, x_n, apar într-o ordine aleatoare.

Date de ieșire

Fișierul de ieșire afise.out conține o singură linie cu două valoari ce reprezintă lungimea minimă totală folosită și numărul de panouri folosite astfel încât toate zonele deteriorate să fie acoperite.

Restricții și precizări

  • 0<L1 0000 < L \leq 1 \ 000;
  • 0<nL0 < n \leq L;
  • 0<kL/20 < k \leq L / 2;

Exemplul 1

afise.in

25 8 3
3 11 6 4 19 15 20 12

afise.out

11 3

Explicație

Zidul are lungimea egală cu 2525 de unități, iar 88 dintre ele conțin afișe care trebuiesc acoperite cu maxim 33 panouri. Se vor folosi toate cele 33 panouri care vor totaliza 1111 unități, acoperind zonele 363-6, 111511-15 și 192019-20.

Exemplul 2

afise.in

10 4 6
7 3 8 1

afise.out

4 3

Log in or sign up to be able to send submissions!